Google Interview Question for Developer Program Engineers


Team: Bing
Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 5 vote

Time complexity = O(n)
Space = O(1)

void getEvenDuplicates()
{
	int number[]={1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9} ;
	int len = sizeof(number)/sizeof(number[0]);
	int tracker=0;

	for(int i=0; i< len; ++i)
	{		
		int shifted = 1<< number[i];
		tracker ^= shifted;
	}
	
	for(int i=0; i< len; ++i)
	{
		int shifted = 1<< number[i];
		if((shifted & tracker) ==  0)
		{
			tracker ^=shifted; // to avoid repeated printing of the number
			cout<<number[i]<<endl;
		}
	}
}

- Khush September 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will work if the numbers are very small. If 10,000 appears, even if you use long long, it still fails.

- wang891010 September 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one Khush. I'd consider it 2 * O(n) but appreciable.

- Orion arm, Laniakea October 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

@Orion arm: Last time I checked, 2*O(n) = O(n)
@Khush:
wang891010 is right, your solution is not O(1), by adjusting your solution to any range of numbers, you are basically using a bit vector of size m, where m is: max-min

- Mike November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this wont work! int has only 32 bits. so any number bigger than 31 will fall off. for example if the array is {50,48,40,50,48,40,35}
"shifted" and "tracker" will be 0 the whole run.

- NotForReal April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi,
If the question is three of them are odd appear times and others are even times, I can solve.
I want you can make sure, is the question correct or not?

- zhangboryan June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zhang: yes solve ,but please give algo, no code

- veta June 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the example he gives is not correct. 5 appears 2 e.g. even amount of times

- james.porcelli@stonybrook.edu September 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi, can you explain the question more detail? what is the "each integer is present an odd huber of time" meaning? Like give us some example.

- zhangboryan June 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Updated.

- gdg June 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
is there any specific range of numbers like 1 to n ?
and also
a XOR a XOR a ---- - -- - - odd times = a
a XOR a ---- -- -- --- - even times = 0
In our case the number that we want to find out will become zero if we perform XOR only.
I am not sure that we can find out the repeated number using XOR only.
Could you please answer am I correct or wrong?
Thanks,
srinivas

- Srinivas June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"is there any specific range of numbers like 1 to n ? "
RE: No, no such thing like that.

- Anonymous June 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

didnt know google had a bing team :) im pretty sure atleast 90% of the questions in this site are not real.

- Anonymous June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how do you know that? and how did you get this "90%" number? by conforming each of these problems?

- harry528tt July 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each bit position from LSD to MSD (for value upto 9 max 4 bit poistions)
Go through the array and move all the values with bit 0 to the left and 1 to the right
have two pointer one from left and right
increment the left pointer until an interger with bit 1 in digit i is encountered
decrement the right pointer until an interger with bit 0 in digit i is encountered
swap these two
proceed above until left < right
This would have split the numbers into two groups
Performing this for all the 4 bits would have grouped the same numbers next to each other
now scan through the array from 0 to n-1
xor i+1..n until the number is different - count the occurence
print if count is even
now the new number to xor was the different one encountered during xor

Total number of scans through the array = no_bits * n + 1 * n = (no_bits+1) * n = O(N)
As the sort / grouping was done inplace no additional space used.
NOTE:Stack space might be used if the split on groups is performed recursively, just the left and right pointers for each recursive call

- Phoenix June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

I realized that no_bits is typically 32( or 64) which is bigger than logn. So it's not better than a sort algorithm which is O(n*logn)

- xiaoxipan July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@xiaoxipan agreed

- Phoenix July 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public class Fun {

    // configured for positive, single digit integers per sample input.
    static final int DIGITS = 1;

    public static void main(String[] args) {

        int[] counters = new int[10 * DIGITS];
        int[] data = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };

        for (int x = 0; x < data.length; x++) {
            int index = data[x];

            if (index > counters.length || index < 0) {
                throw new RuntimeException("input Integer " + index + " out of range for data structure");
            }

            if (counters[index] == 0) {
                counters[index] = 1;
            }
            else {
                counters[index] ^= -1; // XOR with negative 1 to create one's
                                       // complement per question requirement
                // counters[index] = ~counters[index]; // equivalently, use
                // uniary complement operator to create one's complement
            }

        }

        // show the counter results
        // 0 means not encountered
        // +1 means odd
        // -2 means even (one's complement of 1 = -2 and vice versa)
        //System.out.println(Arrays.toString(counters));

        // show the even numbers
        for (int x = 0; x < counters.length; x++) {
            if (counters[x] == -2) {
                System.out.println(x);
            }
        }
    }
}

- AHMED June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

[0, -2, 0, 0, 1, -2, -2, 1, -2, 1]
1
5
6
8

Your data has 2 instances of 5, so it should be in the results.

- AHMED June 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi,
I think you us a very good method, for this question. But in your method the Integer value always less than 10. If we can not know the limit of these integer, may be we can not use your way, because the Space Complexity: O(1), counters[] may take lots of memory, right?

- zhangboryan June 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yea i wouldn't agree thats a great solution because ur making a big assumption on the input if it contains 1 number that is 2^32 -1 then thats a lot of space ur requiring

- james.porcelli@stonybrook.edu September 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why not simply increment counter instead of fancily using xor.

- praveen November 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import Foundation

class Play {
    
    func play() {
        
        let numbers: Int[] = [1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9]
        
        var dataBank: Int = 0
        
        for number in numbers {
            var slot = 1 << number
            dataBank ^= slot // Toggle the bit everytime we find the same number in the sequence
        }
        
        dataBank = ~dataBank // Invert it so now the posistive bits represent the EVEN numbers we are looking for
        
        for number in numbers {
            if dataBank & (1 << number) > 0
            {
                // TODO: The even numbers will appear at multiple times
                println("Even number found: \(number)")
            }
        }
    }

- napostolov June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,
in your method you use Integer as a buffer. If the elements in the array is larger than 32... , how to solve this question?

- zhangboryan June 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is an example of the so sought XOR solution and it works in case the number of possible different integers is less than a certain threshold like 128 or 64. You can always rely on a mapping (hashtable) solution if the elements are in a wide range of possible values.

- Anonymous June 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned int input[] = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};
	unsigned int oddInputs=0;
	for( unsigned int i = 0 ; i < sizeof(input)/sizeof(input[0]) ; ++i){
		oddInputs ^= ( 1 << input[i]);
	}
	
	std::cout << "OddInteger { ";

	for( unsigned int i = 0 ; i < sizeof(input)/sizeof(input[0]) ; ++i){
		if(( oddInputs & ( 1 << input[i])) == 0 ){
			oddInputs |= ( 1 << input[i] );
			std::cout <<  input[i] << " ";
		}
	}
	std::cout << "}";

- Seb June 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we're misunderstanding this a bit. O(1) means constant space - that means the space is not varying with the input n. So in that case we can very well assume an extra int arr[10] and then index the values of the original input straight into arr[value]++ ?

- soum July 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the sample output in the question is incorrect. It should be 1, 6, 8 and 5. From the input, it seems that 5 is repeated twice, which means it should be in the output.

Am I missing something or does the question specify we can arbitrarily pick 3?

- Zhia July 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is for sure needs more questions to ask before attempting to solve,

1. what is the domain size, according to example [0-10] ( we will assume ),
so you just need a constant array, size 10, in this case and pass through the data
increment per index in second array and second pass print even or odd numbers

so memory O(1) - constant, time: N + 10, O(N)

- max July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Try to use a Bit version Trie?
Use a bit (namely, "time") to determine if a node represents a number, so you can use XOR ( time^=1 ) to determine if it appears odd times (if time == 1).
Traverse the trie, print those nodes with time == 1 (You also need to reconstruct the value of the node).

The time complexity is O(32*N) for 4-byte Integers = O(N), and the space complexity is bound by the maximum number of nodes in the trie (2^32). Although it seems large, it's O(1) by definition.

- FrederichCheng July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map

Code:

public static void findEvenOccurringNumbers(int[] a)
	{
		Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

		for (int num : a)
		{
			if (hash.containsKey(num))
			{
				hash.put(num, hash.get(num) ^ 1);
			}
			else
			{
				hash.put(num, 1);
			}
		}

		for (Entry<Integer, Integer> entry : hash.entrySet())
		{
			if (entry.getValue() == 0)
			{
				System.out.println(entry.getKey());
			}
		}
	}

- aviundefined August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space comp. is O(N) ..

- Anonymous October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First sort the Array

public void FindEvenOccurance(int[] arr,int size)
{
int count,j;
for(int i=0;i<size;i++)
{
count = 1;
j=i+1;
while(j<size && arr[j]==arr[i])
{
count++;
j++;
}
if(count %2==0)
Console.WriteLine("Number"+ arr[i]);
i = j - 1;
}
}

- Ashok Gowla August 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args)
    {
        Integer [] input  = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

        findEvenOccur(input);
    }

    public static void findEvenOccur(Integer [] input){

        if(input == null || input.length == 0)
            return;

        HashMap<Integer, Boolean> countingMap = new HashMap<Integer, Boolean>();

        for(Integer i : input)
        {
            Boolean isOdd = countingMap.get(i);
            if(isOdd == null)
                isOdd = false;
            countingMap.put(i, isOdd ^ true);  //even occurence will have false, odd will have true.
        }

        for(Integer i : countingMap.keySet())
        {
            if(!countingMap.get(i))
                System.out.println(i);
        }
    }

O(n) time
O(k) for the hashmap where k = the range of the numbers, and it's k <= n -3. Assume large n and small k, then it's constant.

- benny.chaucc August 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class SortNumber{

public static void main(String []args){

Integer[] hari= {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

ArrayList<Integer> newIn = new ArrayList<Integer>(Arrays.asList(hari));

Set<Integer> finalList = new HashSet<Integer>();

for(Integer a: newIn){
int r = Collections.frequency(newIn, a);

if(r%2 == 0){
finalList.add(a);
}
}

System.out.println(finalList);
}
}

- Rahul August 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class SortNumber{

public static void main(String []args){

Integer[] hari= {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

ArrayList<Integer> newIn = new ArrayList<Integer>(Arrays.asList(hari));

Set<Integer> finalList = new HashSet<Integer>();

for(Integer a: newIn){
int r = Collections.frequency(newIn, a);

if(r%2 == 0){
finalList.add(a);
}
}

System.out.println(finalList);
}
}

- Rahul August 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time COmplexity =O(n)
Space= O(1)

void getEvenDuplicates()
{
	int number[]={1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9} ;
	int len = sizeof(number)/sizeof(number[0]);
	int tracker=0;

	for(int i=0; i< len; ++i)
	{		
		int shifted = 1<< number[i];
		tracker ^= shifted;
	}
	
	for(int i=0; i< len; ++i)
	{
		int shifted = 1<< number[i];
		if((shifted & tracker) ==  0)
		{
			tracker ^=shifted; // to avoid repeated printing of the number
			cout<<number[i]<<endl;
		}
	}
}

- Khush September 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution assumes numbers are in the range [0, 31]. For arbitrary integers it would need a lot of bits.
Comments on a similar solutions in this thread explain how it requires O(logN) memory.

- PG September 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

in ur example I/O 5 has even frequency

- james.porcelli@stonybrook.edu September 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For this question, I think we can do it in O(n) time.
1. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.

The algorithm looks like this:

List<Integer> result = new ArrayList<Integer>();

int temp = num[0];
for (int i = 1; i < num.length; i++) {
temp ^= num[i];


for (int i = 0; i < 32; i++) {
int t = 0;
if ((1 << i) & temp == (1 << i)) {
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
result.add(t);
if (result.size() == 3) {
break;
}
}
}

return result;

- xzySolitaire November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For this question, I think we can do it in O(n) time.
1. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.

The algorithm looks like this:

List<Integer> result = new ArrayList<Integer>();

int temp = num[0];
for (int i = 1; i < num.length; i++) {
temp ^= num[i];


for (int i = 0; i < 32; i++) {
int t = 0;
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
result.add(t);
if (result.size() == 3) {
break;
}
}

return result;

- xzySolitaire November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void numTimes(int arr[]) {

HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int count = 1;
int tempVar;
// Sort array
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[i] < arr[j + 1]) {
tempVar = arr[j + 1];
arr[j + 1] = arr[i];
arr[i] = tempVar;
}
}
}

// add values in hash map
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
count++;
} else {
hm.put(arr[i], count);
count = 1;
}

}

for (Map.Entry<Integer, Integer> e : hm.entrySet()) {
if (e.getValue() % 2 == 0) {
System.out.print(e.getKey() + " ");
}
}

}

- Anonymous February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

run quick sort with O(nlogn) average case, then check if even or odd

public void getEven(int array[], int max){
		Sort(array, 0, max);
		int checker = 1;
		int val = array[0];
		for(int i = 1; i<=max; i++){
			if(array[i] == val){
				checker = checker ^1;
			}
			else{
				if(checker == 0)
					System.out.println( array[i-1]);
				val = array[i];
				checker = 1;
			}
		}
		if(checker == 0)
			System.out.println( array[max]);
	}
	
	private void QuickSort(int array[], int left, int right){
		  int i = left, j = right;
		  int tmp;
		  int pivot = (right-left)/2 + left;
		  while (i <= j) {
		        while (array[i] < array[pivot])
		              i++;
		        while (array[j] > array[pivot])
		              j--;
		        if (i <= j) {
		              tmp = array[i];
		              array[i] = array[j];
		              array[j] = tmp;
		              i++;
		              j--;
		    }
		}
		if (left < j)
			Sort(array, left, j);
		if (i < right)
			Sort(array, i, right);
	}

- Solomon August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

run QuickSort O(nlogn) then check for even/odd

public void getEven(int array[], int max){
		Sort(array, 0, max);
		int checker = 1;
		int val = array[0];
		for(int i = 1; i<=max; i++){
			if(array[i] == val){
				checker = checker ^1;
			}
			else{
				if(checker == 0)
					System.out.println( array[i-1]);
				val = array[i];
				checker = 1;
			}
		}
		if(checker == 0)
			System.out.println( array[max]);
	}
	
	private void QuickSort(int array[], int left, int right){
		  int i = left, j = right;
		  int tmp;
		  int pivot = (right-left)/2 + left;
		  while (i <= j) {
		        while (array[i] < array[pivot])
		              i++;
		        while (array[j] > array[pivot])
		              j--;
		        if (i <= j) {
		              tmp = array[i];
		              array[i] = array[j];
		              array[j] = tmp;
		              i++;
		              j--;
		    }
		}
		if (left < j)
			Sort(array, left, j);
		if (i < right)
			Sort(array, i, right);

}

- solxget August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

assume x1,..,xn: odd times,
y1,..,ym: even

x1^x2^...^xn ^ y1 ^...^ym = x1^x2^...^xm = t.
--> t ^ x[i] < t.
and t ^ y[j] > t.

complex: O(N)
space: O(1)

- lsquang July 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int p[] = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

int cnt = 1;
int n = 17;
int pos;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (p[i] == p[j])
{
cnt++;
pos = j;
for (; pos < n - 1; pos++)
p[pos] = p[pos + 1];
j--;
n--;
}
}
if (cnt % 2 == 0)
cout << p[i] << endl;
cnt = 1;
}

- Ashok Gowla June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Im not sure if this would be the solution.
I would create empty array, and start adding the items of the array. each new addition would do a XOR comparation with the items of the new array. in case XOR result is 0, it means we have, at that moment, a pair, so we can proceed to delete the item from the array. at the end of the full array we would end with the result array.

not really sure that the time complexity is o(N) exactly, but should be pretty close.

- Aleix June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space Complexity should be O(1)
Better read question more carefully.

- Anonymous June 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Bing team at Google!!! LOL

- Anonymous June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The way I would approach this problem is that I would create a bitmask ( assuming that the digits that are being used are 0-9). As I go over the array I would take the bitmask -lets call it x - and take x XOR (1 << num) . When I am done iterating over the array I would go over the bitmask and see which bits have 0.

- Aleksey June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort the array, then compare the items, if they are equal using xOR, leave them in there and try with i+1 (compare xor with 3 elements) if they are odd, then try it with the 4th element. this way we know how many comparations of the numbers we are having and when they are not the same number (xOR is not 0). this way we know which numbers are odd and we can remove them from the array. The comparation index will jump to the last compared item. time complexity o(N) space o(1)

- cris June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you didn't include the time to sort the array. If the array is sorted then its simple XOR start to end which O(n) and space O(1), but what if it is unsorted and sorting may take O(nlogn)

- hmm June 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

5 appears an even number of times but is not included in the output. Typo?

- Anonymous June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

XOR based only? Stop posting "puzzles". Google would never impose idiotic restrictions like these.

- Anonymous June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

It is unlikely Google asked this. And if someone did, the committee SHOULD throw it out (Unless they were busy that day).

- Anonymous June 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Dictionary<int, int> counts = new Dictionary<int, int>();
            int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };            
                        
            foreach( int i in input)
            {
                int count;

                if (counts.TryGetValue(i, out count))
                {
                    counts[i] = i ^ count;
                }
                else
                {
                    counts[i] = i;
                }                
            }

            foreach( var pair in counts)
            {
                if ( pair.Value == 0 )
                {
                    Console.WriteLine(pair.Key);
                }
            }

- MessyHack June 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Dictionary<int, int> counts = new Dictionary<int, int>();
            int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };            
                        
            foreach( int i in input)
            {
                int count;

                if (counts.TryGetValue(i, out count))
                {
                    counts[i] = i ^ count;
                }
                else
                {
                    counts[i] = i;
                }                
            }

            foreach( var pair in counts)
            {
                if ( pair.Value == 0 )
                {
                    Console.WriteLine(pair.Key);
                }
            }

- MessyHack June 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The space complexity of O(1) is little bit on the harsher side but here are the steps to get required output

Step1: Sort the integer array using LSD Redix sort. LSD Redix sort uses O(k.N) time where k is a constant and depends on the length of the value to be sorted. For example for integer it will be 32 bit. It does not depend on the length of the input.

For LSD redix sort, ideally a new array is used to store the indexes of the input elements. But instead due to O(1) space requirement, we can use a a String variable which will store indexes.
So for input 1 appearing 3 times, 4 appearing 2 time and 15 appearing 3 times, the string can be
countString = "1-3_4-2_15-3_... etc
indexString would then be appropriately created identifying the indices for the elements.

Step2: After sorting the array, the array will have some elements 3 times and some 2 times.

Now start from index 0, i=0
If (i ^ i+1 ^ i+2) == i then ignore this number and move i = i+3;
if (i ^ i+1 ^ i+2) != i then print this number and move i = i+2;

Total time taken:
Step1: For LSD redix sort O(k.N) --> k is constant. Space complexity with string hack = O(1)

Step2: For loop O(N)

- Saurabh June 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Redix sort takes O(k+N) space. See wikipedia.

- xiaoxipan June 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

- Open a 2^32 sized bit array (512 mb) and initialize it to all 0.
- Scan the given array, for every integer, "toggle" the corresponding bit:
e.g. for integer 12, if 12th bit is 0, set it to 1, if it was 1 (saw 12 before) set it to 0
-- now, you will have bits set to 1 for odd elements, and bits set to 0 for even elements
- Scan the given array once more, check the bit for every element, if you see a bit 0 for any element, emit that

- Daghan June 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if extra memory can be used, a simple hash map/set does the work whose time/space complexity is both O(n)

- xiaoxipan June 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Inspired by Phoenix's solution I found another solution that doesn't need to alter the input array. I put all the code here: 1. My solution; 2 Solution based on Phoenix's 3 test cases:

#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <iostream>
#include <utility>

#include <vector>

int firstBit1( int x ){
	//given x, return the index of the first 1 bit of x
	for( int i = 0; x ; x >>= 1, ++i ){
		if( x&1 )//test whether the i-th bit of x is 1
			return i;
	}
	return -1;
}

			
bool find2( std::vector<int> &arr, int &a, int &b, int skip ){
	//given a, b occur odd times in arr, others occur even times, return a, b
	//with the extra condition: skip all elements that equal to "skip"
	int x = 0;
	for( int v : arr ){
		if( v==skip )continue;
		x ^= v;
	}
	int bit = firstBit1( x );
	if( bit == -1 )return false;//invalid input

	a = b = 0;
	int mask = (1<<bit);
	for( int v : arr ){
		if( v==skip )continue;
		if( v&mask )a ^= v;
		else  b^= v;
	}
	return true;
}

bool found( std::vector<int> &arr, int a ){
	//check whether "a" occurs odd times in arr
	bool odd = false;
	for( int v : arr )if( v==a )odd = !odd;
	return odd;
}

bool find3( std::vector<int> &arr, int &a, int &b, int &c ){
	a = b = 0;
	int bits = sizeof(int)*8;
	for( int i = 0;i < bits; ++ i ){
		int mask = (1<<i);
		for( int v : arr ){
			if( v&mask )a ^= v;
			else b^= v;
		}
		if( found(arr, a) ){
			return find2( arr, b, c, a );
		}
		else if( found(arr, b) ){
			return find2( arr, a, c, b );
		}
	}
	return false;
}

void createTestCase( std::vector<int> &arr, int &a, int &b, int &c ){
	//3 different numbers a, b, c
	int max = 10, max_occur = 10;
	b = rand()%max;
	if( b == 0 || b==max-1 )b = max/2;
	a = rand()%b;
	c = b + 1 + rand()%(max-1-b);
	std::vector<int> different_numbers(max, 0);

	different_numbers[a] = (2*(rand()%max_occur)+1)%max_occur;
	different_numbers[b] = (2*(rand()%max_occur)+1)%max_occur;
	different_numbers[c] = (2*(rand()%max_occur)+1)%max_occur;

	int n = 0;	
	for( int i = 0;i < max; ++ i ){
		if( different_numbers[i] == 0 ){
			different_numbers[i] = (2*(rand()%max_occur))%max_occur;
		}
		n += different_numbers[i];
	}

	arr.resize(n);
	for( int i = 0, k = 0; i < max; ++ i ){
		for( int j = 0;j < different_numbers[i]; ++ j ){
			arr[k++] = i;
		}
	}

	std::random_shuffle( arr.begin(), arr.end() );
}

void bitBasedGroup( std::vector<int>::iterator from, std::vector<int>::iterator to, int bit, int max_bits ){
	if( bit == max_bits || to <= from )return;

	auto bit0_it = from - 1;
	int mask = (1<<bit);
	for( auto it = from; it != to; it ++ ){
		if( 0 == (mask & *it) ){
			std::swap( *it, *(++bit0_it) );
		}
	}
//	for( auto it = from; it != to; it ++ )std::cout << *it << ' ';
//	std::cout << std::endl;
	
	++ bit0_it;
	bitBasedGroup( from, bit0_it, bit+1, max_bits );
	bitBasedGroup( bit0_it, to, bit+1, max_bits );	
}

void printArray( std::vector<int> &arr ){
	std::cout << '[';
	for( int v : arr ) std::cout << v << ' ';
	std::cout << ']' << std::endl;
}

void bitBasedGroup( std::vector<int> &arr ){
	int max = *std::max_element( arr.begin(), arr.end() );
	int bits = 0;
	for( ; max; max >>=1 ) ++ bits;
	bitBasedGroup( arr.begin(), arr.end(), 0, bits );
}

bool find3ByGroup( std::vector<int> &arr, int &a, int &b, int &c ){
	if( arr.size() < 3 )return false;

	bitBasedGroup( arr );
	
	int X[3], found = 0;
	int prev = arr[0];
	bool odd = true;
	for( int i = 1;i < arr.size(); ++ i ){
		int v = arr[i];
		if( v == prev ){
			odd = !odd;
		}
		else{
			if( odd && found<3 )X[found++] = prev;
			prev = v; odd = true;
		}
	}
	if( odd && found<3 )X[found++] = prev;
	if( found != 3 )return false;
	a = X[0]; b = X[1]; c = X[2];
	return true;
}

int main(){
	srand( time(0) );

	for( int i = 0;i < 1000; ++ i ){
		int X[3];
		std::vector<int> arr;
		createTestCase( arr, X[0], X[1], X[2] );
		printArray( arr );
		std::cout << "a:" << X[0] << ' ' << "b:" << X[1] << ' ' << "c:" << X[2] << std::endl;

		int Y[3];
		find3( arr, Y[0], Y[1], Y[2] );
		std::sort( Y, Y+3 );
		assert( std::equal(X,X+3,Y) );

		find3ByGroup( arr, Y[0], Y[1], Y[2] );		
		printArray( arr );
		std::sort( Y, Y+3 );
		assert( std::equal(X,X+3,Y) );
	}	
}

- xiaoxipan June 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the space complexity is O(1) however the time complexity is O(32*n). Even O(32*n) is also O(n), actually since 32 >= logn, this is bigger than O(n*logn), which means actually we can just sort. So still looking for a real O(n) approach.
By the way, I tried to delete my post but always failed.

- xiaoxipan July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

start with the first element of the array
xor it with the entire array and count the number of zeros.
if it is even, display it and delete its occurrences from the array.
repeat until array is empty or end of array is reached
deleting = O(n)

- Anonymous July 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map

Code:

public static void findEvenOccurringNumbers(int[] a)
	{
		Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

		for (int num : a)
		{
			if (hash.containsKey(num))
			{
				hash.put(num, hash.get(num) ^ 1);
			}
			else
			{
				hash.put(num, 1);
			}
		}

		for (Entry<Integer, Integer> entry : hash.entrySet())
		{
			if (entry.getValue() == 0)
			{
				System.out.println(entry.getKey());
			}
		}
	}

- aviundefined August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

May be this would be better:

public static final int[] findDuplicates(final int[] data) {
    // take a copy of the data.
    int[] sorted = Arrays.copyOf(data, data.length);
    // sort it. This is O(n log(n)) which will be the bulk of our time.
    Arrays.sort(sorted);

    // now scan the sorted data for even-numbered sequences of values.
    int len = 0;
    boolean even = false;
    // sorted[0] is our first sequence, and currently it is not even.
    // note that the scan starts at position 1.
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i] == sorted[len]) {
            // this element is the same as the sequence, so 'count' the even-ness.
            even = !even;
        } else {
            // this element is different to our sequence, it's a new sequence.
            if (even) {
                // the old sequence had an even count, so we 'preserve' it.
                len++;
            }
            // move the value of the new sequence to the 'beginning'.
            sorted[len] = sorted[i];
            // and the new sequence is odd.
            even = false;
        }
    }
    if (even) {
        // the last sequence was even, we preserve it.
        len++;
    }
    // return the first part of the array, which contains the even sequence values.
    return Arrays.copyOf(sorted, len);

}

- Akhil June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1) The solution should be XOR based only.
2) Arrays.sort = Time complexity: O(NlogN)
Expected Time complexity: O(N)

- Bhaskar June 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space complexity: O(1)
Using Hashtable --> O(N)

- Bhaskar June 22, 2014 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More