## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

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

``````#include <stdio.h>

int _tmain(int argc, _TCHAR* argv[])
{
// this is the input array, modify it to change this
unsigned int arr[] = {1, 4, 5, 6, 4, 6, 2};
unsigned int set = {0};
unsigned int unset = {0};
unsigned int xorNum = 0;
unsigned int numOne = 0;
unsigned int numTwo = 0;
unsigned int numThree = 0;
int len = sizeof(arr) / sizeof(arr);

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;
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 j = 0; j < 32; ++j )
{
temp = ( (xorNum >> j) & MASK ) ? set[j] : unset[j];

if ( (temp != xorNum) && (temp != numOne) )
{
numTwo = temp;
break;
}
}

numThree = xorNum ^ numTwo;

printf("Required Numbers : %d, %d, %d\n", numOne, numTwo, numThree);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

slight modification in the algo

``````#include <stdio.h>
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 = {0};
// unset[i] contains the xor of all the numbers whose (i+1)th LSB is unset
unsigned int unset = {0};
unsigned int xorNum = 0;
unsigned int numOne = 0;
unsigned int numTwo = 0;
unsigned int numThree = 0;
int len = sizeof(arr) / sizeof(arr);

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

Comment hidden because of low score. Click to expand.
0

The modified algo fails for following array. First code is right.
{1, 4, 5, 6, 8, 4, 6, 2, 5, 11, 1, 9}

Comment hidden because of low score. Click to expand.
0

arre oo bond anonymous ur input is wrong

Comment hidden because of low score. Click to expand.
0

Amazing!

Comment hidden because of low score. Click to expand.
1
of 1 vote

What if there are k exceptions?

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

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

Comment hidden because of low score. Click to expand.
0

wat will happen if all three have same least sig bit

Comment hidden because of low score. Click to expand.
0

One problem: what if X has no set bits? This is possible. Consider c = a^b

Comment hidden because of low score. Click to expand.
0

"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 .

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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!

Comment hidden because of low score. Click to expand.
0

@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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can those three numbers occur more than twice ? Or they occur exactly once?

Comment hidden because of low score. Click to expand.
0
of 0 vote

where i can find right solution to this problem ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
non_repeating_numbers = 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 ^= non_repeating_numbers[found - 1];
}
count++;
currentByte >>=1;
}
}

return non_repeating_numbers;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

``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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Traverse the array and create a node of a link list if an element is seen first time, else delete the node if repeated (check link list for repetition), a list will be created of the required numbers.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Eugene, Eugene, Eugene. Sigh.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Can you please help me to understand why do we require 2 bits? A 1 bit array of size 4294967295 is sufficient right?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

calculate XOR of all the numbers and the answer will be the number with three occurances.

Comment hidden because of low score. Click to expand.
0

"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.

Comment hidden because of low score. Click to expand.
0

@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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@eugene: You can reduce the consumption by using a vector for the book-keeping (dense) arrays. You don't really need to allocate the whole thing in the beginning.

Yes, in the worst case it is 17GB (or whatever) but that is still O(1) ;-)

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.

### 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.