Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
set[i] contains the xor of all the numbers whose (i+1)th LSB is set
unset[i] contains the xor of all the numbers whose (i+1)th LSB is unset
slight modification in the algo
#include <stdio.h>
#define MASK 0x1
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int arr[] = {1, 4, 5, 6, 4, 6, 2};
//unsigned int arr[] = {1, 2, 3};
// set[i] contains the xor of all the numbers whose (i+1)th LSB is set
unsigned int set[32] = {0};
// unset[i] contains the xor of all the numbers whose (i+1)th LSB is unset
unsigned int unset[32] = {0};
unsigned int xorNum = 0;
unsigned int numOne = 0;
unsigned int numTwo = 0;
unsigned int numThree = 0;
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len; ++i)
{
unsigned int& val = arr[i];
xorNum ^= val;
for (int j = 0; j < 32; ++j)
{
( val & (MASK << j) ) ? ( set[j] ^= val ) : ( unset[j] ^= val );
}
}
unsigned int temp = 0;
int j = 0;
for ( int j = 0; j < 32; ++j )
{
temp = ( (xorNum >> j) & MASK ) ? set[j] : unset[j];
if ( (temp != xorNum) )
{
numOne = temp;
break;
}
}
//xorNum ^= numOne;
for ( int k = j + 1; k < 32; ++k )
{
temp = ( (xorNum >> k) & MASK ) ? set[k] : unset[k];
if ( (temp != xorNum) && (temp != numOne) )
{
numTwo = temp;
break;
}
}
numThree = xorNum ^ numTwo ^ numOne;
printf("Required Numbers : %d, %d, %d\n", numOne, numTwo, numThree);
return 0;
}
The modified algo fails for following array. First code is right.
{1, 4, 5, 6, 8, 4, 6, 2, 5, 11, 1, 9}
Assuming those three numbers have only one occurrence (odd)
XOR of all numbers will give XOR of the three numbers.
X= a^b^c
Now take any set bit from this number
X&~(X-1) will give the least significant set bit.
Now a set bit means that this was set in exactly one of three numbers.
Now take xor of all elements which have this bit set. You get first number.
Take xor of remaining number, you will get xor of other two elements. Now
do similar step sa above that is partitioning based on a set bit , on these remaining numbers, This time xor of these two groups separately will yield other two numbers
"X&~(X-1) will give the least significant set bit . Now a set bit means that this was set in exactly one of three numbers. "
How can u infer this ??
If that bit is set in all the three numbers, then also the corresponding bit is set in the xor of all the numbers.
I think what u suggested to get the first number won't work .
I don't think there's a way to easily recover from the issue I pointed out earlier: that all bets are off when you're XORing 3 or more numbers. Therefore, downvoting because this approach seems fundamentally broken.
@Eugene:
There is a way.
If a^b^c is zero, then instead of a,b,c we compute lsb(a) ^ lsb(b) ^ lsb(c). where lsb(x) is the power of two which corresponds to the least significant bit of x.
This is guaranteed to be non-zero.
--
17GB = O(1), really!
@Eugene:
Basically lsb(a) ^ lsb(b) ^ lsb(c) will give you a bit to bucket/partition on. Now you make another pass through the array.
Basically, if a^b^c = 0, then all you need to do is find one of the set bits of either a or b or c and bucket on that. Taking lsb (and creating the appropriate power of 2) of each number and XORing will give you that.
In fact, the case a^b^c = 0 is the _easy_ case.
If a^b^c = X != 0, then picking a set bit of X (or even an unset bit) does not guarantee the bucketing on that bit will divide a,b,c. a,b,c all could still go into the same bucket!
As to whether or not the approach works. I know there is a solution using XOR (and the above solution is incomplete/wrong, I agree).
What if all three of a, b, c have the same least significant bit? Then you also don't have a bit to partition on.
@eugene: The lsb was in assumption that a^b^c = 0.
In the case S = a^b^c != 0 , the solution uses the following: you try to find the rightmost bit where the numbers differ from S: i.e. compute least_diff(x,S) for each element in the array and take the XOR. And that neatly merges with the above case, so you don't have to treat them separately.
If we convert the problem to: "Find the two non repeated elements....." it will become trivial problem. So here is an idea how to find the third element:
1.) if we XOR all the numbers we will get the bits that are repeated 3 times or Non 3 times (i.e. one time in our case).
2.) so we are looking for the elements that are repeated Non three times and Non even times in the code bellow they I call them "one".
3.) after we have the third number and all we have to do is exclude that number and we have the trivial problem with two non repeated elements.
Here is the Java code for finding the third non-repeted element:
public int getThirdElement(int[] nums) {
int newOne = 0;
int one = 0;
int two = 0;
int three = 0;
int four = 0;
int xorAll = 0;
for (int num : nums) {
xorAll ^= num;
newOne = four & num;
four &= (~newOne);
four |= three & num;
three &= (~four);
three |= two & num;
two &= (~three);
two |= one & num;
//one &= (~two);
one = (~(four | three | two)) & num;
one |= newOne;
}
return getNum(nums, one);
}
private int getNum(int[] nums, int oneRep) {
int result = 0;
int diffBit = oneRep & ~(oneRep - 1);
for (int num : nums)
if ((num & diffBit) > 0)
result ^= num;
return result;
}
How about this for a solution.
public static int[] positions(int[] numbers)
{
byte[] vector = new byte[(int)Math.pow(2,32)/8];
int value = 0;
for(int i = 0; i < vector.length; i++)
{
vector[i] = 0;
}
for(int i = 0; i < numbers.length; i++)
{
int index = numbers[i]/8;
int shifts = numbers[i]%8;
vector[index] ^= 1<<shifts;
//value ^= numbers[i];
}
int[] non_repeating_numbers = new int[3];
non_repeating_numbers[2] = value;
int found = 0, count = 0;
while(found < 3)
{
byte currentByte = vector[count/8];
for(byte index = 0; index < 8; index++)
{
if((currentByte & 0x01) == 1)
{
non_repeating_numbers[found++] = count;
//non_repeating_numbers[2] ^= non_repeating_numbers[found - 1];
}
count++;
currentByte >>=1;
}
}
return non_repeating_numbers;
}
1) keep a single integer, k
2) xor the integer with a 3rd degree polynomial of all integers given as input
3) at the end solve the remaining equation, this gives you three integers, all positive if you setup polynomial right
you can extend this for k integers
a*x^3+b*x^2+c*x+d
. so when you calculate this for an input, XOR the value. On a second thought, I realize coming up with a orthogonal equation is hard, not always giving you real numbers, integers. what about a bloom filter like solution? hashing different bits of numbers so that hash values go in different bins? for three integers memory requirement is quite small and it can be extended to k integers.
If you really must require a (fairly obvious) explanation for the downvote: I don't think this can be the solution we're looking for. While technically O(1), it could be horribly inefficient if the input array isn't all that large. Also why 8 GB? If it's two bits per number, it's 1 GB.
Can you please help me to understand why do we require 2 bits? A 1 bit array of size 4294967295 is sufficient right?
You need to know whether the number occurred not at all, once, or twice. That's 3 logical possibilities, so we need 2 bits per number.
No need of 2 digits if we can XOR the a[num] with 1 (assume all the a[elements] initialized with 0) . If at all an XOR with 1 returns a 0, we can assume it is a duplicate and return it. Only thing is we don't know whether a number occurred or not, which is not required in the current case.
Two bits because "Every number appears twice, except three of them" does not imply those three occur exactly once. One could appear 15 times, other 29 and the third 490.
The calculation might be off, but you can have arrays (with default value 0) without actually initializing it. So, we save the cost of initializing it (which is what is probably bothering Eugene).
And of course, this is probably not the solution they are looking for.
This answer was added to specifically point out the idiocy of the problem.
calculate XOR of all the numbers and the answer will be the number with three occurances.
"Two bits because "Every number appears twice, except three of them" does not imply those three occur exactly once."
Very true. So the two bits are being used to distinguish between zero, one, two, and more than two occurrences.
"The calculation might be off, but you can have arrays (with default value 0) without actually initializing it. "
No, you can't. Either your language zeros out arrays or it doesn't. If it does, it costs you no matter what. If it doesn't, you must do it. I'm also concerned about the unreasonable memory footprint in addition to performance.
@Sunil: No. You misunderstood the problem. There are three different numbers with one (or 1 or >2, depending on your interpretation) occurrences.
@Eugene:
Yes you can! (and the language is irrelevant).
See this: research. swtch. com/sparse
The page is aptly titled "Using uninitialized memory for fun&profit." and the technique has been known since the 1970s (and was apparently first published by trio Aho, Hopcoft, Ullman).
What is an unreasonable memory footprint really depends on the situation... (though I agree with you in this case, and as I said earlier this was posted in an annoyed response to the question).
That's an interesting technique. I actually used something similar to it in one of my projects about a year back, but not exactly like that. My technique wouldn't have been powerful enough for this, but this technique actually requires you to store an integer for every possible value, so now you need something like 16GB (4 billion possible values * 4 bytes/int) + 4*n bytes (dense set representation) + 1 GB (size of the bitset from our discussion before) > 17 GB extra space!
Thanks for teaching me about this technique, though. It's still a useful trick to keep in mind and consider using at times.
And then the language is not irrelevant. You need to use a language that doesn't clear arrays to 0 before handing them to you.
I have been thinking about a solution to this problem for quiet some time now.
Before I propose my solution, here is some points that my code will use
1 = 1^1^1 or 1^0^0
0 = 0^0^0 or 0^1^1
ie, if we calculate the xor of all the numbers (xorNum), then
1) if a particular bit is set in the xorNum, then
a) either it is set in all the 3 numbers,
b) or it is set in only one of them
2) Similarly, if a particular bit is unset in the xorNum, then
a) either it is unset in all the 3 numbers
b) or it is unset in only one of them
Though my code I will try to find 1b and 2b condition mentioned above to find a solution to this problem.
Here is my solution
- pranaymahajan August 18, 2012