## Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

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

the algo is atleast O(n/2) which is O(n);
take 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;

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

That'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).

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

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

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

It works. here a[5] == a[4]

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

for { 1,2,3,1} you will not find any i such that a[i] == a[i-1] OR a[i] == a[i-2].

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

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

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

How about array of size 6 and the array elements as 1,2,1,3,1,4

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

sam, please think twice before posting. It also works.

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

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

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.

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

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

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

time O(N/4)

``````while(startIdx<endIdx)
{
if(array[startIdx++] == array[endIdx--]) break;
}``````

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

dont waste ur 2 seconds. this is not correct.

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

Check Ur code for I/P sample:1626364656 and post me what U get....

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

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

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

This definitely seems to be the only working solution with O(n) and constant space

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

And without tampering the original array

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

This one seems correct.. nice

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

This one seems correct.. nice

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

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

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

solution above by gautam is correct except he forgot to check wraparound. so if u reach end, u need to compare last element with the first. i guess a[i+3] will also work ,but checking wraparound will be elegant i think..

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

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

4 , 1 , 2 , 4

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

solution is almost ok, just check wraparound, i.e check last element with first one..i guess this should suffice..any other corner cases.??

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

n/2 + 2

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

the question is not clear...how about the array {1, 2}?

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

Do a quicksort of the array and then return its middle element.

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

One more idiot...lol.

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

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

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

#include <stdio.h>

int main()
{
int a[] = {1 , 2 , 3, 1 };
int n = sizeof (a )/ sizeof(a[0]);

int i;
for ( i = 0; i < n; i++ ) {
if ( a[i] == a[(i+1)%n ] || a[i] == a[(i+2)%n] ) {
printf("%d ", a[i] );
break;
}
}
getch();
return 0;
}

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

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

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

The above problem can be solved using the concept of the hashmap, where we will first count the frequency of all the integers and then, we will traverse the hashmap and compare check of the frequency if found greater then n / 2 then output the number.

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.