"Coding is just like talking to a unknown girl. Once you talked to her with guts, the next time you'll never afraid",Really? Yes , try it Now !!!
Everything here is for education and learning purpose only , individual holds rights on outer posts/links etc.
Team Cracking The Code
About Me
▼
Thursday, August 4, 2011
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
Hash table to calculate the frequency of each number. and then scanning the whole of hash table to know the if there is a number which has freq >= N/10
@anshul yes this idea works , bus it requires O(n) space,a more space efficient approach to use Moore Voting Algorithm that doesn't requires any extra space, its used to find majority element in an array , isn't it ?
Correct me if i am wrong or any other idea you have to do it efficiently ?
Hi I have question regarding Moore Voting Algorithm As per algo AAADDCCDABCCCAA I should get A as the majority however I will get C as the answer...Correct me If I am wrong
Hash table to calculate the frequency of each number. and then scanning the whole of hash table to know the if there is a number which has freq >= N/10
ReplyDelete@anshul yes this idea works , bus it requires O(n) space,a more space efficient approach to use Moore Voting Algorithm that doesn't requires any extra space, its used to find majority element in an array , isn't it ?
ReplyDeleteCorrect me if i am wrong or any other idea you have to do it efficiently ?
Cheers !!!
Shashank
Hi I have question regarding Moore Voting Algorithm
ReplyDeleteAs per algo
AAADDCCDABCCCAA I should get A as the majority however I will get C as the answer...Correct me If I am wrong