## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

Found this solution
Question: You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.

Fastest way to find that single integer
eg:
Input: [2,1,4,5,1,4,2,2,4,1]

Answer: I couldn't solve this question myself at first go in O(n) with O(1) space. Searched for it and found an excellent answer here. Sharing the answer and explanation for that:

int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes, x ;

for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}

printf("\n unique element = %d \n", ones );
return 0;
}

Explanation:
The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.

To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

1st example
------------
2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

2nd example
------------
4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.

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

the solution may work but the explanation is wrong...try with [12,8,12,12] and check what happens at all the five step in the second iteration

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

The code works well.
but explanation is really wrong.
For example the statement
"ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once."
is completely wrong - debugged the program several times and generally it is not true.
Can anybody explain why the code works ?

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

kuch bhi,
Just tell me how do you people find out weather an element is appearing for 1st time or 2nd time or 3rd time, for that we need to hash them, and that require space,

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

This has been well explained on geeksforgeeks
geeksforgeeks-dot-org/find-the-element-that-appears-once/

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

nice search jagat....finally a valid explanation

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

From stack overflow...

``````def special(lst):
ones = 0
twos = 0
for x in lst:
twos |= ones & x
ones ^= x
not_threes = ~(ones & twos)
ones &= not_threes
twos &= not_threes
return ones

Explanation:

If the problem were this: "one element appears once, all others an even number of times", then the solution would be to XOR the elements. The reason is that x^x = 0, so all the paired elements would vanish leaving only the lonely element. If we tried the same tactic here, we would be left with the XOR of distinct elements, which is not what we want.

Instead, the algorithm above does the following:

ones is the XOR of all elements that have appeared exactly once so far
twos is the XOR of all elements that have appeared exactly twice so far
Each time we take x to be the next element in the array, there are three cases:

if this is the first time x has appeared, it is XORed into ones
if this is the second time x has appeared, it is taken out of ones (by XORing it again) and XORed into twos
if this is the third time x has appeared, it is taken out of ones and twos.
Therefore, in the end, ones will be the XOR of just one element, the lonely element that is not repeated. There are 5 lines of code that we need to look at to see why this works: the five after x = A[i].

If this is the first time x has appeared, then ones&x=ones so twos remains unchanged. The line ones ^= x; XORs x with ones as claimed. Therefore x is in exactly one of ones and twos, so nothing happens in the last three lines to either ones or twos.

If this is the second time x has appeared, then ones already has x (by the explanation above), so now twos gets it with the line twos |= ones & x;. Also, since ones has x, the line ones ^= x; removes x from ones (because x^x=0). Once again, the last three lines do nothing since exactly one of ones and twos now has x.

If this is the third time x has appeared, then ones does not have x but twos does. So the first line let's twos keep x and the second adds x to ones. Now, since both ones and twos have x, the last three lines remove x from both.``````

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

the solution might work if the bitwise operators are doing what the logic above says it is doing but the explanation of the 5 statements given above is totally wrong...for instance how is ones & x = ones when x appears the first time? for example if the array was of the form 12,8,.....and current value of x was 8 then ones = 12 and 12 & 8 = 8 and then 12 ^ 8 = 4 then not_three will become 2^32-1 (all 1) and the next two steps lets ones and two unchanged....this analysis at least proves that it is not at every iteration that ones and twos will hold the xor's of the elements till that time that has apperared once or twice? do let me know if something is wrong in my analysis...

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

Can you give simple example of this?

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

Good problem.
we consider the bit separately
v0 is the set whose occurrence time mod 3 = 0
v1 is the set whose occurrence time mod 3 = 1
v2 is the set whose occurrence time mod 3 = 2
we know that each bit must exactly in one state {mod3 = 0, or mod 3 = 1. or mod 3 = 2)
so for a new number, the only thing may happen is that some bit is in vi goto v( (i+1)%3) if both vi and x contains that bit.

``````#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define mp make_pair
#define pb push_back

typedef long long LL;

const int MAXN = 333;

int a[ MAXN ]=  {12,1,12,3,12,1,1,5,3,3};

int main(){
int v0, v1, v2, n = 10;
v0 =v1 = v2 = 0;
for(int i = 0; i < n; ++ i) {
int r0, r1, r2,x=a[i];
r0 = v0&x; r1=v1&x; r2=v2&x;
v0 =(v0^r0)|r2;
v1 =(v1^r1)|(x^r1^r2);
v2 =(v2^r2)|r1;
}
cout << v1 << endl;
return 0;
}``````

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

Superbly explained.
Let me know if you find better explnation than this!

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

1) Sort the array. O(nlogn)
2) Then for every element keep checking the next element till end. If current element == next Elelement increase the counter. if current Element != next Element then check counter. If counter is zero then return that element. If counter is not zero then make counter zero and proceed. O(n).

space complexity is O(1).

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

Take an element and take the first bit and divide them into two groups ...
ie all the elements with 1's on one side and 0's on the other side ... now count the left side elements and right side elements ( use the quick sort divide strategy ) and take the side which is not the multipple of 3 now again divide recursively untill you get 3 elements on one side and one elements on the other side .. that one element is the culprit ...

This is the best which i can get ... should try some logical operators

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

int appearOnce(int arr[], int N)
{
int ones=0, twos=0;
int threes;
for (int i=0; i!=N; ++i){
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}

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

#include <iostream>
#include <map>
using namespace std;

int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3};
map<int, int> m;
pair<int,int> p;

int size = sizeof(arr)/sizeof(arr[0]);

// Insert
for(int i=0; i<size; i++)
{
p.first = arr[i];
p.second = 1;

if ( m.count(arr[i]) > 0)
{
m.at(arr[i])++;
}
else
m.insert(p);
}

// Print
for( map<int, int>::iterator i=m.begin(); i != m.end(); i++)
{
cout << i->first << " " << i->second << endl;
}

return 0;
}

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

``````// binary sort : O(log n)
// 1, 1, 1, 2, 3, 3, 3, 12, 12, 12

if array[length] != array[length - 1]
print arr[length
else
{
for( i=0; i < ( length - 1 ) /3 ; i++)
if ( arr[i*3] != arr[i*3+2] )
{
print arr[i*3];
break;
}
}``````

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

Use Pivot strategy.If after every trials the pivot is at 0th Index then the number is unique .if number is equal to pivot it will be on left side else on the right side.
Example

12 12 12 3 3 1 2 1 3 1

for 1
1 1 1 12 12 12 3 3 3 2

for 2
2 1 1 1 12 12 12 3 3 3

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

Thanks for good session.Put a trail on skillgun.com for more interested questions,asked in android developer interview section.

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

check for more skillgun.com

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

geekForGeek solution 2 is the best and its generalized solution and works for any k.
---------------source geefForGeek----------------------
Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence.
Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000
Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of fourth bits%3 = (1)%3 = 1;
Hence number which appears once is 1000

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

Take the XOR sum.we will get the sum of unique elements.
Take the sum of original array
As we know each number is repeated 3 times we multiply xor sum with 3
Now missing number is
(Xorsum-sum)/2
Why we have divide the difference because the the non repeated number is taken 3 times in xor sum

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

``````float sum;
for(each element)
{
sum = (float)element * 0.333;
}
float number = take fractional part of sum ;
number *=3;
printf(neartestIntegerOf(number))``````

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

No That is wrong. This does not work for {12,1,12,3,12,1,1,5,3,3 }.

Your approach will give you 2 where as actual answer is 5.

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

This will also not work if the missing number is a multiple of 3

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

it will only work if the lone number was 0, 1, or 2..mod 3 of any number wull be either of those 3 values

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

Yes. this won't work!

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

this is wrong when the number appeared 3x times

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.