## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

You mean the element which appears at least n/2 times? This is a classic problem...

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

@Itcecsa
what is dominator? can you explain the question better?

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

a dominator of a array is an element which appears more than N/2 times, where N is the size of the array.

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

BST?

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

It doesn't work for {5, 4, 5, 4, 5, 4, 5, 4, 5}

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

It doesn't work for {5, 4, 5, 4, 5, 4, 5, 4, 5}

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

step1:: We can find dominator in O(n) time. & O(1) Space complexity
step2 :: array size 7
e.g 1) 1112222 dominator 2
e.g 2) 2222111 dominator 2
e.g 3) 1212122 dominator 2
e.g 4) 1231231 there is no dominator
e.g 5) 1231233 there is no dominator
e.g 6) 3321233 dominator is 3

***************************************
note:: my below solution, could not find dominator for e.g 6) case
***************************************
step3:: take a variable count, cout =1 , denom= A[0].
step4 :: for (i =1 ;i<n ; i++)
increase count by 1 when current element is equal to dom elemet
decrease count by 1 when current element is not equal to dom elemtn

step 5:: if count > 1 then there is denominator , else there is no denominator

// Code for this solution

dom = A[0]; // initially assume dominator is first element
domFirstIndex = 0; // dominator first index location
count = 1;

``````for( i=1; i< n; i ++ )
{
if( A[i] != dom )
{
count --;
if( count == 0 || count <0 )
{
dom = A[i] ;
count = 0 ;
domFirstIndex = i;
}
}
else
{
count ++;
}
}

if( count > 0 && (domFirstIndex <= n/2))
{
printf("\n dominator is %d", dom);
}
else
{
printf("\n there is no dominator \n");
}``````

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

your approach seems correct. I did not undrstnd y r u checkin for domFirstIndex<=n/2??

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

dominator presents in array atleast n/2 times. So its first index location should be on or before n/2 th location.

If we do not check this condition, the above algo will return 3 as dominator in I/P "112233".

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

thanks. I get it now. But u see according to the question asked above we hav to return index of any element which contains dominator.. So if we go by your approach we'll get index of the dominator in domFirstIndex.. n to check for the case you mentioned we can loop thru the array one more time to count if the dominator occurs more than n/2 times.. that will make the complexity O(2n)~O(n).. Plz comment..

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

Yes, you are right. we need to loop one more time to print dominator all indexes.

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

It doesn't work for {5, 4, 5, 4, 5, 4, 5, 4, 5}

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

Saw a solution for this question at codingissue.com. It is also known as "super majority".

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

@Siva.Sai I checked your code and tried to analyze.
Lets say the input array is [3,1,3], here dominator is clearly 3.
Initialize: dom = 3 (i.e A[0]), domFirstIndex=0
Iteration 1: i=1, (dom!=A[i]), therefore count--, then count=0, dom=1, domFirstIndex=1
Iteration 2: i=2, (dom!=A[i]) therefore count--, then count=0, dom=2, domFirstIndex=2

After the loop ends, if (count>0 && domFirstIndex <= n/2), both conditions fail here but still there was a dominator in the input array.

Please correct me if I understood anything wrong.

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

My solution is not perfect. It does not work for all cases. in your example case it does not give correct solution.
As I mentioned earlier my sol does not work for below e.g 6

e.g 1) 1112222 dominator 2
e.g 2) 2222111 dominator 2
e.g 3) 1212122 dominator 2
e.g 4) 1231231 there is no dominator
e.g 5) 1231233 there is no dominator
e.g 6) 3321233 dominator is 3

***************************************
note:: my solution, could not find dominator for e.g 6) case
***************************************

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

You are almost there! The if-else order matters.
See stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-an-array
The algorithm works for case 6 as well.

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

The Boyer-Moore Majority Vote Algorithm fails to find correct majority in the below input arrays

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};

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

@sivasai,

Wont your logic fail for this input { 3,6,3,5,3,4,3,2,3}?

Please correct me if i am wrong..

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.