Amazon Interview Question
Software Engineer / DevelopersI forgot 2132...
So that means IF the list size = 4, check +1,+2,+3 ... if not, just +1,+2
Or just wrap around the list on the last two elements...
For example on 2132 .. the checks would go:
2: 1,3
1: 3,2
3: 2,2
2: 2,1 <-- duplicate found...
How big to you think your hash table should be if in worse case scenario all unique elements appear before duplicated?
//'n' is the size of the array 'arr[]'
/*according to the question 'n' has to be even
if 'n' is odd then there is a confusion on what will
be the middle element - unique or non-unique*/
int element(int arr[],int n)
{
int tmp=0,ele;
for(int i=0;i<n/2;i++)
{
tmp^=arr[i]; //xor operation
}
if(tmp==0)
ele = arr[i-1];
else
ele = arr[i];
return ele;
}
Time complexity - O(n/2) = O(n)
Start building a binary tree. The moment you hit a previously found node , you have found your non unique element . It will reach an output in less than n iterations.
NUmber which occured more that n/2 times in the array :
We will sweep down the sequence starting at the pointer position shown above.
As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element e:
* If the counter is 0, we set the current candidate to e and we set the counter to 1.
* If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
I think just need to check next element for each element, but we need to check next two and previous two element resp. in case of first and last element
ex: arr 1 5 2 5 3 5 4 5
a[0]a[1] a[0] a[2]
1 : 5 1 : 2
5 : 2
2 : 5
5 : 3
3 : 5
5 : 4
a[6] a[7] a[5] a[7]
4 : 5 5 : 5 ...... duplicate found
int findRepeated(int * array , int n)
{
for(int i=0,int j = i+1 ; i<n-1 ; i++,j++)
if(array[i]==array[j]) return array[i];
if(array[0]==array[2]) return array[0];
if(array[1]==array[3]) return array[1];
return NOTFOUND;
}
comments ?
three pointer pointing 3 consecutive elements will do the work.
proof: the problem can stated as we have x no of unique element and x no same elements. I want to prove that there will be at least one case where one unique element will be between two same element - thus the two neighboring same and 1 unique kind can be pointed by three pointers and can be compared.
lets assume we've x unique elements and there by (x+1) places to insert x same elements to form the given array. At any point of all possible insertion we can see that either two or more same elements are together (thus can be detected by three pointer comparison). if this is not the case then there will be at most one scenario where two similar element will have 2 unique element between them and rest all cases will have exactly one unique element between them - thus can be detected by three pointer comparison.
---i think this logic is known as Principle of Pigeon Hole to geeks :-)
Algorithm:
i=0 //1st index
j=1 //2nd index
k=2// 3rd index
if elements pointed by i, j and k does not have two common elements
then
i=k+1
j=i+1
k=j+1
else
the common element is the similar element
end if
//Note only i is sufficient, for simplicity j and k are used
kg has essence of solution. I convinced by self a little bit differently though.
Suppose you have n/2 unique elements and n/2 same elements in an array of size n (which is even by the way). The same elements exist somewhere in this array by definition, so consider the arrangement where they are maximally distant from each other, meaning each same element is as far away from any other same element as possible.
Clearly we would not want any two same elements to be neighbors.
So we would have an every-other arrangement like "x 1 x 2 x 3 x 4 x 5" or "1 x 2 x 3 x 4 x 5 x" since there are equal numbers of unique and same elements.
Suppose a same element was a distance of 2 from another same element. How would you move from the most distributed arrangement above to the new arrangement with a gap of 2 between same elements? It would have to result in violating the condition that two same elements are neighbors.
This means that for each element, compare it with next neighbor and next next neighbor. If it is equal then that's the "same" element.
int a[10] = {1,3,2,2,4,5,2,2,6,2};
int res;
for (int i = 0; i < 10;) {
res = a[i++];
if (res == a[i++] || res == a[i++])
break;
}
its all bulllshit....
guys this is simple majority finding algorithm...just google out for majority finding algo, and u'll get the solution...
dude.......can u be a bit more polite........particularly if you dont know the answer......your answer is wrong.......majority finding algorithm only works when there is one element which occurs at more than 50% of the time.....and in our case there is no such element.......the closest is one element which occurs 50% of the time.....
I guess a proof can be given by using a pigeon hole principle.
Algorithm:
i check for a non-unique element in a(1),a(2),a(3). If not i try in a(4) a(5) a(6).. and so on..until end of array
(i give this algorithm because it has an easier proof, not because it is more efficient)
Proof:
If there are no unique element in any such disjoint triplets, then the number of non unique elements cannot be more than ceil(n/3). Thus, there will be one such triplet.
v can find this in a single traversal of the array u know..
hav 2 variables a,b and follow the pseudo code below:
i/p: 1 2 3 2 2 4
1)initiate a=0,b=0;
2)read the element and store it in 'a' provided b=0;
3)b is incremented only when next element is equal to a.
4)b is decremented provided if(b>0) and when a!=next element
5)do from step2 till end
finally the value stored in a is the answer
i ll simulate it
a=0
b=0
reading 1
a=1
b=0 (rule 2)
reading 2
a=2
b=0(rule 2)
reading 3
a=3
b=0(rule 2)
reading 2
a=2
b=0(rule 2)
reading 2
a=2
b=1(rule 3) //b alone incremented bcoz a=currelement
reading 4
a=2
b=0(rule 4) //here a is not changed bcoz b was 1 before reading 4//
tell me if any suggestion..
How about this.
Since 50% are same number and 50% are unique, there is atleast one instance where the non-unique(repeating) numbers are next to each other unless the repeating numbers are alternating between the unique numbers.
So make one pass to see if there are any consecutive repeating number. If none, then check the first four numbers and find the repeating number.
NITW Guy:
Your method works. But "make one pass", how much expensive is that "one pass".
The key is do not make one pass.
Scan first 4 numbers, it costs 6 comparisons.
Move to next 4 numbers, it costs 12 now.
Keep going on n/6 time, if we do not find a duplicate number, go for one more time. This time we are sure to find the duplicate number.
Since each time, if we are not lucky, we get the duplicate number say d, and other 3 unique numbers.
If it goes on n/6 time, we scan through n/2 unique numbers plus d. We will surely get at least 3 d's and perhaps one more unique number(considering n= odd). So, the algorithm has n+4 comparisons.
I haven't read the other solutions so my solution might be a subset or super set of other solutions.
Here is the pseudo code ( Assuming n is even, though for odd as similar solution would suffice)
1. Break the array into groups of 2 elements each
2. Compare the two elements ( this will order n as there will be n/2 comparisons)
3. Now there can be 2 cases
1. In one of the group the element is same, Hence that element is non unique.
2. All groups don't have same element. This means that there is one unique and one non unique element. Hence just compare any 2 groups randomly and you will get the non-unique element. This will 3 more comparison hence order of algorithm remains O(n)
not read the solution but
i think simply traverse the array....keep a note of two consecutive elements before the current element..i.e check a[i] with a[i-1] a[i-2]...worst case first n/2 elements are unique and last n/2 are repeated so wud traverse half the array....
i=2;
while(i<n)
{
if(a[i]==a[i-1]||a[i]==a[i-2]) {cout<<a[i]; exit;}
}
Traverse the array, check your current position + 1 and + 2 for the same value... If at any time while traversing the list you find a duplicate, then you've found the answer. Here are my test cases it works on:
- Rob February 19, 20081232
2213
1322
1223