Amazon Interview Question for Software Engineer / Developers


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>
#define MASK 0x1

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[32] = {0};
	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;
	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;
}

- pranaymahajan August 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pranaymahajan August 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pranaymahajan August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

arre oo bond anonymous ur input is wrong

- anonymous August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Amazing!

- LoocalVinci August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

What if there are k exceptions?

- LoocalVinci August 31, 2012 | Flag
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

- Anonymous August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wat will happen if all three have same least sig bit

- Anonymous August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- navin.nitjsr August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.yarovoi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.yarovoi August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 13, 2012 | Flag
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?

- ImagineTheFire August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

where i can find right solution to this problem ?

- rahulpandeyham August 12, 2012 | Flag Reply
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;
 }

- GKalchev August 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 18, 2012 | Flag Reply
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

- soho August 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- soho August 17, 2012 | Flag
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.

- okaysh August 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Eugene, Eugene, Eugene. Sigh.

- Anonymous August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hari@hbiz.in August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- hari@hbiz.in August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sunil August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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.yarovoi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 13, 2012 | 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