Find the number occurred odd time in Array

Currently, I encountered a question in interview "find a number which occurred odd time in Array". Friends in fact the first you think answer by using Hashtable and iterating all the elements from list and counting the number of time the element occurs in list.

But if is you remenber the college days and XOR digital gate this is very simple question to answer.

if the 1 XOR 1 = 0 and 1 XOR 0 = 1 so if same number are bitwise XORed it will give 0 and if odd time EXORed gives the number it self.

for ie 1 XOR 1 = 0 but 1 XOR 1 XOR 1 = 1 so here is simple program to find single number which occurred odd time in array.

public class FindOddOccuranceInArray {

	public static void main(String[] arg) {
		int[] nums = new int[] { 1,2,2};
		int val = findOddOccur(nums);
		System.out.println("val :: " + val);
	}

	public static int findOddOccur(int[] nums) {
		int val = 0;

                // all even number will be XORed to 0 and even number will

                // remain
		for (int i = 0; i < nums.length; i++) {
			val ^= nums[i]; /bitwise xor
		}
		return val;
	}
}

Hashtable implementation in JAVA

I came across many forums and blogs where I saw questions to implement Hashtable but there is no satisfactory answer for that question. I tried here to give the answer, how to implement hashtable in java using Array.

First lets go in hashtable fundametal. The Hashtable stores key value pair and the retrieval and insert of element time complexity is O(1).
To store the elements in hashtable there is need to calculate hashkey which is use to store value at specific index on array. The function "hash" in program calculates the hash code once the hash code is calculated modulo is taken by the size of Array to map the key at particular index of the array. remember to minimize collision take size at prime number.

There are possibility of collision on elements at particular index if the hash value calculated same for the two different key and hence the old value will be over written in by new value. To avoid this situation there are multiple way to implement the logic but here we are avoiding this logic. We will focus how hashtable interal structure and how does it works. I have implemented two main important method "get" and "put"

package com.interview;



public class MyHashTable<K, V> {

	/* take the capacity as prime number to reduce the collision */

	private static int SIZE = 31;

	/* initialize array to store value */

	private V[] tableValues = (V[]) new Object[SIZE];



	public synchronized V put(K key, V value) {

		if (value == null) {

			throw new NullPointerException();

		}

		int index = hash(key.hashCode()) % SIZE;

		tableValues[index] = value;

		return value;

	}



	public synchronized V get(K key) {

		int index = hash(key.hashCode()) % SIZE;

		return tableValues[index];

	}



	/**

	 * method calculates the hash code

	 */

	private synchronized int hash(int h) {

		h ^= (h >>> 20) ^ (h >>> 12);

		return h ^ (h >>> 7) ^ (h >>> 4);

	}



	public static void main(String arg[]) {

		MyHashTable<String, String> table = new MyHashTable<String, String>();

		/* store 10 values in Hashtable */

		for (int i = 0; i < 10; i++) {

			table.put("key" + i, "value" + i);

		}

		/* retrive values */

		for (int i = 0; i < 10; i++) {

			System.out.println(table.get("key" + i));

		}

	}

}

Implement Array Iterator in JAVA

Iterator is very important part of programming, I don't think that any programmer has not ever used this Iterator. have you ever think what is the internal structure of the Iterator and how does it works? Generally it is used with collection to iterate over elements of the collection.

One of the question asked in Google interview to implement Iterator's methods "hasNext" and "next" for the array. the The Iterator must be generic to accept different kind of array. In fact, this question can be asked for different data structure like

Implement Iterator for binary tree, for linked list etc.

But after this implementation you would have fair idea of iterator and how to implement it

Here is the detail class code. The main method contains the code to test the class functionality.



package com.interview;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArrayIterator<T> implements Iterator<T> {
T[] a;
int counter = 0;

public ArrayIterator(T[] a) {
this.a = a;
}

@Override
public boolean hasNext() {
return counter < a.length;
}

@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
T t = a[counter];
counter++;
return t;
}

@Override
public void remove() {

}

public static void main(String[] a) {
Integer [] array = new Integer[] { 1, null, 4, 3, 5 };
ArrayIterator<Integer> it = new ArrayIterator<Integer>(array);
while(it.hasNext()){
System.out.println(it.next());
}
}
}



I would love to have your comment on code and also your questions. Please privde your feedback on code.