Amazon Interview Question Software Engineer / Developers
#define INVALID_ELEMENT -1
// There can only be one such element not more
int ElementWithMoreThanHalfOccurances(int array[], int length)
{
int count=0, element,i;
element = array[0];
count = 1;
for(i=1;i<length;i++)
{
if(element==array[i])
{
count += 1;
}
else
{
if(count==0)
{
element = array[i];
count = 1;
}
else
count -= 1;
}
}
if(count<= length/2)
return INVALID_ELEMENT;
else
return element;
}
@selvan: What is the input where you see it won't give you correct results?
@gopi: No thats not the assumption.
Why so many crappy people all around? People post code apparently without testing at all. What output this code gives for simplest input like "1 2 1".
here length = 3, and count = 1, i.e. count <= length/2. 1 appears twice here. Why it's too hard for you test your own code?
@hmm.. you can be nice dude!! after all everyone is trying to help each other
anyways the above code is the voting algorithm
cs.utexas.edu/~moore/best-ideas/mjrty/example.html
1. For the above solution to work we should remove the if check "if(count<= length/2) return INVALID_ELEMENT; else" and always return the element.
2. This solution works only if we for sure know if there exists an element with which is repeated n/2 times if not we should go one more pass to verify that...
Read the algo in above link and it will be clear
again what happens if input is a[] ={3,4,3,3,4,3,4}.
At the end of iteration count = 1 and element = 4
and if we simply return element then it will be wrong because correct answer is 3.
Please help me out....
There are O(n) time and O(1) space algorithms which don't involve sorting. Search for Finding Repeated Elements paper by Jayadev Misra.
well, if the list has more than n/2 elements repeated, then that, repeated, element would be the median of the list when sorted. So, we can apply selection algorithm to find the median of the list in O(n) time. That means we need to find out the (n/2)th rank element in the list. Similarly, we can find (n/4)th rank element in O(n) time.
Guys, if you have any better solution, please share.
but that will not confirm that this element was repeated n/2 times in list. it will always result some number as median.
If a number repeats more than n/2 times in an array, the median must the number itself. The reverse is surely not true. So, it just gives an indication. You've to scan the array to count how many times the median element occurs indeed.
This method can be extended to 2nd part of the problem by finding n/4th, 2n/4th and 3n/4th element. These are the candidate (there can't have more than 3 elements each repeats > n/4 times). Count the frequency of each of n/4th, 2n/4th, 3n/4th element to validate the indication.
Isn't selection O(n^2)? It's impossible to sort within O(n) time, plus you're counting the element, so your solution is already only as good as sort and count.
Selection can be done in O(n). Maybe the best selection _you_ can come up with is O(n^2), does not mean others can't do O(n).
Lookup median of medians algorithm on the web.
Selection can't be harder than sorting. Then why you believe it'd be O(n^2)? Median of medians algorithm leads to O(n) selection, and O(nlogn) for selection-based sorting (i.e. quicksort).
Using STL nth_element() you can code above in less than 15 lines in O(1) space and expected linear time. Hash is another solution, as pointed by someone else. However, many interviewers not always like hash based solution due to its worst case behavior + space requirements.
another solution can be using a HashTable to keep the number -> count mapping.
complexity:
scanning the array, - O(n)
insert in HashTable - O(1)
get the number with count > n/2 , n/4 - O(1) [hashtable lookup]
Space complexity - O(n) [worst case]
I thought of the same thing. Use hash tables and all your problems will be solved. If the element is not present, add it to the hash table and initialize its value to 1. If it is present in the hash table, simply increment its value. Once all the elements are processed, check for elements whose values are >= n/2. The complexity will be O(n) as hashtables have constant time insertion and fetching !
i think to find aan element ocuuring more than n/2 times just easy in O(n) algorithm and we can use the moores voting algorithm here
but to extending the problem like n/4 and something like that i think we have to sort first and then we can have the result simply iterating through the list :)
Majority algoritm is the way to go and it already solved above (with minor errors)....
even for n/4 we use the majority algorithm... just reuse the same approach but now ignore the last found majority element (i.e., the one which is more than n/2 times) in the array which running the algo
Moore's algorithm can't be applied to find n/4. If we apply again to find n/4 element, you will get element that is second most common (could be n/4 but not necessarily)
Moore's algorithm is "could be algo" .. we need to have one more pass to confirm anything... either it be n/2 or n/4 ..
excerpt from Moore's... ( find which element of a sequence is in the majority, provided there is such an element)
@vamsu: you are misinterpreting the definition of "majority" here. Majority means more than half (only 1 such element can exist in an array). Applying Moore's algorithm you'd find one element that occurs more than n/4th time. Explained here (2nd post):
ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1216999786
But you can't find all 3 of such elements that occur more than n/4th time using this method. Read the 2nd reply to get clarified.
thanks for the clarification...
I was in a impression that we should to find the n/4 element in the same array which we found n/2 ... if that isn't the case I totally agree
"Design an algorithm to find all elements that appear more than n/2 times in the list. Then do it for elements that appear more than n/4 times."
consider array[] = {1 1 1 1 2 3 2}
have an array of size 10,, a[10] = { 0 all elements }
for i from o to sizeof(array): // O(n)
a[array[i]]++ ;
now sort the array based in the value (neglecting value of 0)
should take O(logn) coz numbers r repeated in the sequence n/2 , n/4 , n/8
a[] now has the solution :):)
Wrong complexity analysis. Firstly, The input is NOT GUARANTEED to have duplicates. Hence, sorting a[] basically takes O(nlogn) as elements can be all unique in array[]. Secondly, you assume input range is known, which is not given anywhere. Thirdly, what you suggest is basically using hashtable to count frequency. Then, why do you even need sorting? You can just scan through hash table, i.e. a[] taking the top 3.
Wait. If an element repeats more than n/2 times, doesn't it have to be the middle element when sorted?
Go to you desk, and work on paper! Why ask such silly things without trying yourself? In an interview, no one will come to help you to sort out such silly things :P
@vamsu: are you sure JAGAT understood when you write "of course". If he understands just with this, why the hell he couldn't at first! So, isn't it better to construct people in logical ways (the old paper-and-pen style, working with example, drawing tree/graph blah blah) rather spoon-feeding quickly digestible food, which doesn't help to build CONFIDENCE in a person.
And just to say that JAGAT just spammed the thread asking something that have been clarified by "lol" above. Excerpted from his reply "If a number repeats more than n/2 times in an array, the median must the number itself. The reverse is surely not true. So, it just gives an indication. You've to scan the array to count how many times the median element occurs indeed."
thats correct jagat...! nice catch... :)
for n/4 you just need to pick 3 numbers.... the n/4th n/2nd and 3n/4th after sorting list.(where n is the length of list)
now we can apply counter on only these three numbers.
It will optimize our algo upto some extent...!!
@hmm.. agreed to you on "of course"
in general I would like to see people being polite when we are trying help out each other... even your above reply to the comment "Anonymous on August 14, 2011" Fn: ElementWithMoreThanHalfOccurances was arrogant to me
and in fact you mislead that post... check my reply to that comment above ..anyways PEACE :)
Its a simple Moor's Voting algorithm. For n/4, just do a simple modification to it. This algo finds the element repeated >=n/2 times in a set of elements. Its complete implementation is at wiki, so see it. In case a pseudo code is needed do post for it. Time complexity of this algorithm is O(n).
lol..... why people don't read existing posts before replying? Why they are too restless to write up something crappy!
Applying Moore's algorithm you'd find one element that occurs more than n/4th time. Explained here (2nd post):
ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1216999786
But you can't find all 3 of such elements that occur more than n/4th time using this method. Read the 2nd reply to get clarified.
I'm eager to see what is your "do a simple modification"... Post your solution. I'd catch bugs in it!
void main()
{
int a[10];
int i,check=0,count=1,c;
clrscr();
printf("Enter a");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
c=a[0];
for(i=1;i<10;i++)
{
if(c==a[i])
{
count++;
check=1;
}
else if(c!=a[i] && count>1 && check==1)
{
check=0;
continue;
}
else //if(c!=a[i] &&count>=1 && check==0)
{
count--;
if(count==0)
{
c=a[i];
count=1;
}
}
printf("\n the no is c =%d",c);
}
printf("\n \nthe no is c =%d",c);
}
For n/4.
1) Find the median of the array ( O(n) ) and partition the array around the median
2) Check if median is repeated n/4 times (O (n))
3) Take the left and right parts of the array
4) Check for an element that is repeated more than 50% of elements. If there exists such an element then it is repeated more than n/4 times in the original array
ex: If there are 20 elements, then n/4 = 5.
Partion around the Median --> Partion around position 10
Check if the element at positoin 10 is repeated more than 5 times
Check if there is an element in array from 0..9 that is repeated more than 5 times
Check if there is an element in array from 11..19 that is repeated more than 5 times
Sort the array, iterate over it incrementing a counter while you are at the same number. Anytime the counter goes over n/2, print/record/store the element.
- Anonymous August 14, 2011You now have what you wanted.