Google Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
what if the numbers are all odd and unique. then bit0 count will be 32. The above algorithm would printout a wrong answer right?
hsong's algorithm says: count the number of times each bit is 1 across all the numbers (store in arr count[]). After reading m numbers, count[0] will give the number of times bit 0 is 1 among all m numbers. If greater than m/2, set the output element bit 0 to 1.
Output should be the number with freq > m/2. If the input is a stream of unique odd numbers then count[0] will be 32. What do we print output in this case?
This approach doesn't work! The frequency of the element of interest is at least M/2, which can very well be exactly M/2. Thus, if the count of some bit is M/2, that bit can be either 0 or 1. In the worst case, all 32 bits have counts equal to M/2 which makes all the 2^32 combinations feasible.
Remarkably clever algorithm. I think it works in all cases, even when all numbers are odd as suggested in above posts.
To infinitystreet, cipher and JuggNutt: The frequency of the element of interest is larger than m/2 (not "at least m/2"). Thus it will not happen that all numbers are unique.
Let's say that we have three numbers, 1, 3 and 4. The count is going to be 1 1 2 for the last 3 bits, 0 for the rest. Then, since m/2 is 1.5, this approach will give 1 as a result which is an incorrect result.
consider a sequence 3, 14, 10, 2
0011 = 3
1110 = 14
1010 = 10
0010 = 2
--------
summing up bits set to 1 gives us:
--------
2141
according to your algo, the repeated number is 2.
which is wrong.
am I missing sth?
Your missing that the problem statement guarantees that there is one number with > m/2 entries!
This is simple? Yes. Clever? Well... that is subjective.
But the problem with this is that this is O(M w) where w is the word size of the underlying machine, and assumes we actually know what it is and actually uses O(w log M) space.
It works
you have to set all the bits having count > m/2
if bit 0 and bit 3 repeat more than m/2
then ans is 1001 = 9
I don't think Anonymous above was saying it doesn't work...just that it's less efficient than the most optimal solution, which is true.
It's still a relatively efficient solution, however, given that people are probably assuming here that w is a constant. I think the reason most people (including myself) upvoted this is because this was a fresh take on a classic problem.
#include<stdio.h>
int main() {
int c=0,id=-1;
int n;
while(printf("Enter a number:") && scanf("%d",&n)){
if(id != -1 && id != n)
c--;
else if(id == n)
c++;
if(c == 0){
id=n;
c++;
}
}
printf("The number is : %d",id);
return 0;
}
class MajorityVoting
{
public static void main (String args[])
{
int arr[] = {2, 2, 3, 3, 3, 2, 2, 3, 2, 3};
System.out.println (findMajor (arr));
}
public static int findMajor(int[] arr)
{
int curr = arr[0];
int count = 1;
for (int i=0; i< arr.length; i++)
{
if (curr == arr[i])
count++;
else
count--;
if (count == 0 && (i+1) < arr.length)
{
curr = arr[i+1];
count = 0;
}
System.out.println (arr[i] + " " +curr+ " " + count);
}
if (count <= 0)
return -1;
return curr;
}
}
private int findMaxFreq(ObjectInputStream in) {
int freq = 1;
int key = Integer.MINIMUM;
while ((temp = in.readInt())!=null){ // continue reading the stream till you exhaust it
if (temp == key) // its old number
freq ++;
else {// its a new number
freq --;
if(freq <=0){
// time to change the key
key = temp;
}
}
After exhausting the stream, the number with freq > m/2 will be stored in the key.
count the bits or 1s in the stream of each 32bits positions.
- hsong November 20, 2011you will end up with 32 counts of 1s (each representing the number of 1s seen at the bit position).
Compare it with m/2. If it is bigger, that bit is 1. else that bit is 0.