## Amazon Interview Question

Software Engineer / DevelopersThat's a poor O(n) solution. It eats up O(n) memory.

Here is the better one :

I think you simply need to parse through the array keeping a backlog of two elements. As N/2 are equal and the rest is guaranteed to be distinct there must be one place i in your array where

a[i] == a[i-1] OR a[i] == a[i-2]

iterate once through your array and you have complexity of roughly 2*N which should be well inside O(N).

@Anonymous - your approach wont work .. say array size is 6 and the elements in array are 1,2,3,4,1,1

your logic will fail here

Divide array into different grps of size 3. Any grp will have that 2 or more elements common.

One more approach using Mnte Carlo.

Just select any two var at rand, and check if they r equal.

Chance that they are equal is 1/2*1/2 = 1/4 hence not finding prob = 3/4

if same fine

Else

repeat

So on an average you will have to do 4 samplings to find the repeated element.

which is almost constant time, if n >> 4.

Form the Build-Max-Heap from the list of elements , it takes at Max 0(n) time . In the Max-Heapify() algorithm include check for equality , if any element becomes equal then that is the repeating element. The only chance is that all leaf elements becoming equal , just do a manual check once to avoid that case , this can be done 0(2) , so total time 0(n) time.Correct me if i am wrong

int getDupElem(vector<int> &arr){

if ( arr.size() <= 2 ) return MININT;

for(int i = 0; i < arr.size()-2; i++){

if ( arr[i] == arr[i+1] || arr[i] == arr[i+2] ) return arr[i];

}

return MININT;

}

chk for a[i+3] also, then it will be fine (original question is more than n/2 times)

for eg 2 1 3 2.. in this 2 is the answer

@anonymous who posted on June 30th 2010, ur solution does not seem to be correct for this case :-

4 , 1 , 2 , 4

let n be the size of array

therefore p=n/2;

if(a[i]==a[i+1] || a[i]==a[i+2] || a[i]==a[n+i])

return a[i];

I think this will reduce complexity

check the array in blocks of 2 like {0,1} , {2,3} , {4,5} ....

The repeated element can be in each of the different blocks or 2 of them can be in one block .

If two of them are in one block , it can be easily identified in the first round of checking.

If each of the repeated element is in different blocks , then after the first check , none of arr[i] == arr[i+1] will match . In the second round we just check elements in indexes {0,1,2,3} to find out which one is repeated

the algo is atleast O(n/2) which is O(n);

- ram June 30, 2010take a sample of (n/2)+1 elements . That sample will have the repeated elt ( pigeon hole principle.

1. implement a hashmap ;

2. check whether elt exists in the map ; if so return the elt

3. else insert elt in to hashmap;