Puzzle #13 – A Google Interview Question
July 25, 2008The following puzzle was given to me by a friend who claimed it was given in a Google interview. If you can confirm or debunk this claim just post a comment – until then I am sure the headline will generate some traffic 🙂 .
The original question as it was given to me was:
Given an array with 2n+1 integer elements, n elements appear twice in arbitrary places in the array and a single integer appears only once somewhere inside. Find the lonely integer with O(n) operations and O(1) extra memory.
Now let’s transform this to a more digital-design-like problem. Given an SRAM of depth N and some arbitrary width K, which is filled with 2n+1 non zero values (for completeness – the rest of the 2^N – (2n+1) are all zeroes). n elements appear twice – in different places in the SRAM, while a single value appears only once.
Design a circuit with the minimum amount of hardware to find the value which appears only once.
Adventures in ASIC Digital Design 
Hi,
is the algorithm allowed to be destructive on the dataset? In other words: can I mess up the array as long as I find the item? Are all the n+1 items mutually different, or is it allowed to encounter let’s say four times “5”?
Philip
you can destroy the contents if you wish although it is not necessary IMHO.
and an item might appear 4 times or any number of even or odd times – you will then have to pair the items and find the odd one out.
remember – the idea is to use the minimal amount of hardware!
If it boils down to pairing I was very skeptical about the complexity.
If you pair all elements starting from the first array item you need (2N-1) operations for the first search. The next paring search will be 2N-2 and so on. The amount of operations sums up to: (2N-1)+(2N-2)+…+(2N-(2N-1)) (note that you have 2N-1 sum terms in total). I always thought that these kind of algorithm is in O(N^2). Since it appears that for each item you have to touch more than a constant amount of others.
But apparently they are not.
(2N-1)+(2N-2)+…+(2N-(2N-1))
= (N-1)2N-(1+2+…+(2N-1))
= (N-1)2N – (2N-1)(2N)/2
= … cancel out …
= N
which is in O(n)… well that’s not exactly the solution in terms of hardware but explains why the algorithm is better than I thought 🙂
I hope that this is correct, I literally used yesterday’s shopping list to write down the calculation…
Philip,
I think you are over-complicating.
I am sure you will hit yourself on the head seeing the more simple solution.
Think simple! and thanks for sharing your thoughts online.
N.
algorithm:
int solution(int* arr)
{
int i, res;
for (i=res=0; i<2n+1; i++) res^= arr[i];
return res;
}
hardware:
connect an N-bit counter to the address line of the SRAM and XOR the Data_Out with a K-bit register. When the counter overflows the value in the register will be the answer.
agree… over-complicated 🙂
How about a x bit counter such that 2^x >= 2N+1; and a k bit register.
start with lsb, x bit counter will count no. of 1s in lsbs of all 2n+1 digits. Then 2nd bits and so on upto msbs (kth bits).
LSB of the counter is assigned to the corresponding value in your k-bit register, when full- is your answer.
Or even more simple way is
have a (2N+1) XOR gate and apply the same logic to store value in a k-bit register.
in k iterations you will get answer in your k-bit register.
Following sln was given by Tzachi –
Sln is gr8 but doesnt it meets the exact requirement of the problem:
Sln should be solved in N Operations with O(1) extra memory — this particular sln takes 2n+1 operations and O(2) of memory.
algorithm:
int solution(int* arr)
{
int i, res;
for (i=res=0; i<2n+1; i++) res^= arr[i];
return res;
}
(a) The requirement was: ‘Find the lonely integer with O(n) operations…’ not N operations.
(b) It’s obvious that it can’t be done in n operations. 50% of the times your algorithm (or any other) won’t even get to read the lonely integer in the first n operations.
(c) O(2) = constant = O(1)
read the 1st element from memory.store this output after xor-ing with K bit register(initial all ‘0’), in the same register.
repeat this step for 2n+1 times. values stored in K bit register, will be rquired answer.
I think Philip right.
Well, Here’s my solution – Using an approach similar to the counting sort algorithm:
the buffer can hold 2^K different values – this is a constant number.
I will use a 2^K size buffer (Inititalized to 0) and run over the N SRAM values. For each value read, I will use the value as an address to the 2^K deep buffer, and change the state of it (XOR with the previous value). When I’m done, after O(N) operations, all that is left to do is go over the 2^K buffer and look for a “1”….So basically this is O(N+2^K), but if we say 2^K is a constant it sums up to O(N).
(Something that is worth mentioning is that the google question has K as 32bit – for an integer number….)
I’m pretty sure there’s a simpler answer.
Here is my solution. Quite simple, but have to figure out the circuit yet:
Alternatingly add and subtract contents in consecutive memory locations. By the time you reach the end, you would either have a +ve or a -ve number. The magnitude of that number would give the odd number.
lets say the array is 3,3,4,4,5, your solution will yield
3+3-4+4-5 = 1 ( not the number)
I have a solution when the width of SRAM is just the depth/2 +1 (for 1K+1 deep SRAM it is 10 bits). In this case, use the contents to address a 1K+1 bit array of another SRAM and toggle the bits (initially it is cleared to all ‘0’). Finally after the last operation, translate the 2n+1 bit array in to address to get the odd number.
If the width of SRAM is arbitrary, then I have a CAM solution where there are n/2 + 1 CAM locations and the solution is simillar to above. Nir, is CAM allowed and am I going in right direction?
Thanks,
Sathya
successively XoR the bits of all the numbers. The result will be the odd number.
example: if the array is 3 3 4 6 6 7 7 ==>
xor 011 with 011 = 000
xor 000 with 100 = 100
xor 100 with 110 = 010
xor 010 with 110 = 100
xor 100 with 111 = 011
xor 011 with 111 = 100
Hence 4 is the odd number.
doesn’t work with 3, 6, 5, 5, 4, 6, 3.
what was the intention anyway with such a quick solution?
double check your math Vijay. It DOES work
xor 011 with 110 = 101
xor 101 with 101 = 000
xor 000 with 101 = 101
xor 101 with 100 = 001
xor 001 with 110 = 111
xor 111 with 011 = 100
which is 4, the odd member. XOR is a linear operation, and any number n xor n will result in zero, so all redundant members of the array will be eliminated, leaving only the odd member that occurred once to be xored with 0, which will be itself.
Hi,
I interviewed for the associate product manager position at google, you can read it up here
http://ferozeh.com/Interviews/Google/google.php
Example puzzles by a Googler. Good insight into problem solving at google.
http://googlepuzzles.blogspot.com/
I’m not him. I just wrote about the puzzles. 🙂
Some Puzzles at http://technical-interview.com/puzzles.aspx
We can use a parity generator for this.
Hi,
Good solution, but what if I am interested in knowing the address of the lonely number?
-Anirban
cool … xor clears duplicates … and leaves just one true self – it should be called the Jeez of logic gates 😉