Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
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");
}
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".
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..
@Siva.Sai I checked your code and tried to analyze.
Lets say the input array is [3,1,3], here dominator is clearly 3.
According to your code:
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.
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
***************************************
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.
You mean the element which appears at least n/2 times? This is a classic problem...
- Anonymous May 04, 2012