Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Sounds like the solution is correct. What is the intuition or math behind this approach? Why does this work? Any links/references will be appreciated.
I think its correctness can be convinced in two ways: 1. Proof using pigeon-hole principle 2. Proof by induction.
If we let M denote the count of majority element and N the count of all the elements,
an assertion(A) can be made as - 'By the end of the algorithm, the value of counter is at least 2M-N and the current number holds the majority number'.
1.Since M>N/2, we can place the elements in such a way that the majority number, m alternates with other N-M numbers of the set. Again, since M>N/2, using pigeon-hole principle, M-(N-M) (= 2M-N) majority numbers have to be consecutive. This makes the counter to have a value of at least 2M-N and sets the current number to m. The rest of the traversal through the array decrements the counter by at most 1(when m is not the last element of the array) or retains the current value(when m is the last element of the array) and hence the current number is not set to any value other than m.
Induction: Induction is on the size of the set
Base case: A majority element exists in a 3 element set. Let the tuple
(v, n) denote the counter value and the current number respectively. Assertion holds in this case as can be seen by the following possible permutations.
m e m
(1,m) (1,e) (1,m)
e m m
(1,e) (1,m) (2,m)
m m e
(1,m) (2,m) (1,m)
m = majority element, e = any other element
Inductive Step: By inductive hypothesis, suppose the assertion A holds for N elements with M majority elements. There are 2 cases:
1. If we add another majority element to the set, assertion A continues to hold
2. If we add a non-majority element e then there are two cases:
a. After adding e, M>(N+1)/2 holds. Then A holds.
b. After adding e, M>(N+1)/2 does not hold. Then add another m so the invariant M>(N+1)/2 holds and consequently A holds.
I am hoping that I have not made fallacy in my argument. Nonetheless, corrections fixing my arguments are always welcome.
Yup, that's the Moore voting algorithm
When we move the pointer forward over an element e:
If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
Thanks to share "voting algo", it's really number magic
But I have concern, I think "voting algo" only works if existence is >= N/2 otherwise how it will find less than N/2 occurrence and returns null element.
"Voting Algo" also works for no sequential number.
Q. says the numbers are sequential and occurrence may be less than N/2, so I can use a mapping but in a different way ...not exactly map
numbers starts from 1 then maintain N sized array
put the number count according to number in that corresponding index like 1->0, 2->1...
when a count reaches >= N/2 then stop
but will google allow this ?
static void majority()
{
int[] arr = { 1, 1, 2, 3, 4, 1, 6, 1, 7, 8, 1, 1, 2 };
int mjr = 0;
int cnt = 0;
int maxmjr = 0;
int maxcnt = 0;
for (int i = 0; i < arr.Length; i++)
{
if (cnt == 0) mjr = arr[i];
if (mjr == arr[i]) cnt++;
else cnt--;
if (cnt > maxcnt)
{
maxmjr = mjr;
maxcnt = cnt;
}
}
cnt = 0;
for (int i = 0; i < arr.Length; i++)
{
if (maxmjr == arr[i]) cnt++;
}
if (cnt > arr.Length / 2) Console.WriteLine(maxmjr + " " + cnt);
}
static void majority()
{
int[] arr = { 1, 1, 2, 3, 4, 1, 6, 1, 7, 8, 1, 1, 2 };
int mjr = 0;
int cnt = 0;
int maxmjr = 0;
int maxcnt = 0;
for (int i = 0; i < arr.Length; i++)
{
if (cnt == 0) mjr = arr[i];
if (mjr == arr[i]) cnt++;
else cnt--;
if (cnt > maxcnt)
{
maxmjr = mjr;
maxcnt = cnt;
}
}
cnt = 0;
for (int i = 0; i < arr.Length; i++)
{
if (maxmjr == arr[i]) cnt++;
}
if (cnt > arr.Length / 2) Console.WriteLine(maxmjr + " " + cnt);
}
This is actually a working version - count majority element in first iteration and check in second iteration.
public int getMajorityNumber(int[] inputArray) {
if(inputArray == null || inputArray.length == 0) {
System.err.println("Empty array");
return -1;
}
int maxCountNumber = inputArray[0];
int count = 1;
for(int i = 1 ; i < inputArray.length; i++) {
if(inputArray[i] == maxCountNumber) count += 1;
else {
if(count > 0 ) count -= 1;
else {
count = 1;
maxCountNumber = inputArray[i];
}
}
}
return maxCountNumber;
}
First sort the array and then check if the adjacent elements are same.If yes then increment the count everytime and whenever a the count is greater than n/2 then print the element.Here us the code.
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b)
{
return (*(int *)a-*(int *)b);
}
int checkForNumber(int arr[],int n)
{
int i,count=1;
for(i=0;i<n-1;i++)
{
if(arr[i]==arr[i+1])
count++;
else if(arr[i]!=arr[i+1])
count=1;
if(count>n/2)
{
return arr[i];
}
}
return 0;
}
int main()
{
int arr[]={1,1,1,1,2,2,2,2,2};
int n=sizeof(arr)/sizeof(arr[0]);
qsort(arr,n,sizeof(int),compare);
int i=checkForNumber(arr,n);
if(i==0)
printf("No such number");
else
printf("Number that occurs more than n/2 is %d ",i);
}
can we do this...
1.maintain a hash while scanning input and check for n/2 condition and report..
public int getMajorityNumber(int[] inputArray) {
if(inputArray == null || inputArray.length == 0) {
System.err.println("Empty array");
return -1;
}
int maxCountNumber = inputArray[0];
int count = 1;
for(int i = 1 ; i < inputArray.length; i++) {
if(inputArray[i] == maxCountNumber) count += 1;
else {
if(count > 0 ) count -= 1;
else {
count = 1;
maxCountNumber = inputArray[i];
}
}
} return maxCountNumber;
}
No I am not assuming a sorted array.
I am having a single pass over the array and finding the element occuring the max number of times.
I decrement the count whenenver a different element is found than the current max.
Since the element of our requirement is appearing more than n/2 times its count will remain at the end of the pass.
maintain a counter and store the current number. If next number is same increment the counter, if different then decrement counter. If counter becomes zero, then store the next number as current number and set counter to 1, like a fresh start. After itertation is done, you will be left with a current number. Traverse the array once more to check if it is really majority or not. O(n) complexity.
- Anonymous June 15, 2013