Microsoft Interview Question Interns
Country: India
Interview Type: In-Person
Moore's voting algorithm gives the right answer
only if it has the majority element.
Otherwise, it gives a wrong answer,
and there is no indication it is not the actual majority.
For example,
AAABBBC, will give the current status (C,1) at the end.
Hence, given an answer, we have to check
whether it is the actual majority.
Step 1: Moore's voting algorithm -> this will give one element as Majority element.
Step 2: Make one more pass on array. Count the element obtained above. If count >= len/2 then there is a majority element and that is the one obtained in step 1.
if count <len/2 that means array has no majority element.
Just start pushing all the elements into hash map and increment the count on insertion. Store maximum count in a local variable.
Check this count at length /2 + 1 if its not greater than 1 - quit
similarly check it at length / 2 + 1 if its not greater than 2 - quit
Perhaps this would be the most optimum with complexity O(n).
Assumption : there EXISTS a majority element
Logic : keep a record of majority element candidate and its count so far, if the next number matches, increase the count, else decrease the count, if count = 0, set candidate = current number
Time Complexity : O(n)
int candidate = 0;
int count = 0;
for i = 0 to n - 1
if(count==0)
candidate=a[i];
else if(a[i]==candidate)
count++;
else
count--;
end for
print candidate
This is wrong. Here you are making assumption that the first element in the array itself is the majority element and that's wrong. Majority element could start from any index in the array till length/2.
i don't think your algorithm will work on input { 2,1,2}. (the input array isn't sorted}
Actually whatever element the candidate holds at the end (irrespective of its count at the end), will be the majority element(if there exists one)
For eg: {2, 1, 2}
when i = 0, arr[i] = 2, Start with candidate = 2, count = 1;
when i = 1, arr[i] = 1, candidate = 1, count = (1-1)+1 = 0. Since arr[i] != candidate we decrement count, then change candidate element whenever count reaches 0, and then increment count for this new value of candidate.
when i = 2, arr[i] = 2, candidate = 2, count = 1-1+1 = q (similarly)
So at the end candidate = 2 (There will always be a candidate element at the end of the algo)
So, now 2 is the majority element if there exists one in the array. To be sure, just runa scan once again and maintain a counter only for 2. If it is > n/2 then 2 is the answer
nice solution but needs a bit of correction...
initialization is not done properly...
candidate=a[0];
count=1;
this should be the initialization...then the algorithm will yeild proper results
Posting in the correct thread.
With corrections as mentioned by other genius...
First iteration gives you a probable candidate with highest votes but that candidate may not be in majority per definition of the question.
So you have to run additional loop to make sure that candidate has >N/2 votes.
1.Create linklist having data part,count and link part;
data will store the value.
Count will store the no of duplicate of data.
next will link to next node.
e.g.
struct linklist{
int data;
int count;
struct node *next;
}
2.travers the linklist to find node having the maximun value of count;
public class MajorityElement {
//Moore's Voting Algorithm
public static Integer majorityEle(int[] array) {
if (array == null && array.length == 0) {
return null;
}
int candidate = 0;
int count = 1;
for (int i = 1; i < array.length; i++) {
if (array[i] == array[i - 1]) {
count++;
} else {
count--;
}
if (count == 0) {
candidate = i;
}
}
count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == array[candidate]) {
count++;
}
}
if (count > array.length / 2) {
return array[candidate];
}
return null;
}
public static void main(String[] args) {
// int[] array = {3,3,4,4,5,3,3,4};
int[] array = {2,4,2,5,2,2,6,6,6};
System.out.println(majorityEle(array));
}
}
public static boolean CompareWithOtherElements(int [] S, int data, int start, int end ){
for(int i = start; i<= end; i++){
if(S[i] == data){
return true;
}
}
return false;
}
public static int FindMajorEl(int [] S , int start, int end){
boolean Found = false;
if(end - start == 0){return S[start];}
if(end - start == 1){
if(S[start] == S[start + 1]){
return S[start];}
}
int mid = ((end - start + 1) / 2);
int ret = FindMajorEl(S, start, start + mid - 1);
if(ret != -1){
Found = CompareWithOtherElements(S,ret,start+ mid, end );
}
if(Found == false){
ret = FindMajorEl(S, start + mid, end);
if(ret != -1){
Found = CompareWithOtherElements(S,ret,start,start + mid -1);
}
}
if(Found){ return ret;}
else {return -1;}
}
Moore's Voting Algorithm
- Bruce October 24, 2012