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;
	}
}

String Reversal in Java, Efficient way

This is very famous question for the interview to reverse the given String. In fact there are multiple ways to implement this program, but the efficient way is here what I given here. Same thing can me implemented using recursive programming as well.

package com.interview;

public class StringRevarsal {

	public static void main(String[] args) {

		String reverseThis = "Please Reverse Me";

		System.out.println(reverse(reverseThis));

	}

	static String reverse(String reverseMe) {

		char[] charArray = reverseMe.toCharArray();

		int endIndex = charArray.length-1;

		int startIndex = 0;

		while (startIndex < endIndex) {

			char temp = charArray[startIndex];

			charArray[startIndex] = charArray[endIndex];

			charArray[endIndex] = temp;

			startIndex++;

			endIndex--;

		}

		return String.valueOf(charArray);

	}

}

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.

Multiply Other elements of Array

Interview Question :

Given an array A[], multiply all other elements except the current element and produce the other array O[].

Given Array A={5,2,3,6}

Output Array O = {36,90,6030}

The first element of the output array is 2*3*6 leaving 5

same way second element of output array is 5*3*6 leaving 2.

When you solve the problem keep in the mind that the solution should be time and memory efficient.

Solution :

Alright, When you see the problem, nothing comes out from your mind but simple double for loop. Let's implement using double for loop.

public long[] multiplyElements(int[] a){

//declare and initialize output array elements to 1

long[] o = new long[a.lenght];

for(int i=0;i<a.length;i++){

o[i]=1;

}//end init foor



for(int i=0;i<a.length;i++){

for(int j=0;j<a.lenght;i++){

  if(i==j) continue;

  o[i]* = a[j];

} //ends inner for

} // ends outer for

return o;

}

If you notice this operation takes two for loop means n^2 time to solve the problem. Do you think to avoid n^2 time to solve this problem ?

think...... think.....

Oh yes where is a way to go other way around to solve same problem.

simple logic : multiply all the elements in array first and loop through elements and divide the total by current element which will give the same output as we needed and time complexity will be n+n as there will be two loop 1) for multiplied elements and another for dividing total

so if we consider to calculate for 1000 elements

time taken by double for loop will be n^2 that is =>1000000 compare to later solution which takes n+n=>2n==>2000. Isn't that wonderful ?

Better Solution :

public long[] multiplyElements(int[] a){

long[] o = new long[a.lenght];

long total = 1;

for(int i=0;i<a.length;i++){

  total*=a[i];

}//end init foor



for(int i=0;i<a.length;i++){

  o[i] = total/a[i];

} // ends for

return o;

}

Welcome to Onsite Interview Blog

Friends,

There are occasion after onsite interview we want to share the questions asked during interview session. I would like to share some of the most difficult technical questions asked by the highly tech savvy companies like google, yahoo, salesforce and many others during onsite interview. We will discuss mostly in Java but the same questions may be applied other technical language. I would appreciate to join, discuss and share your interview questions and experience.