Google Interview Question for Developer Program Engineers


Country: United States




Comment hidden because of low score. Click to expand.
8
of 8 vote

public boolean validateByte(int n) {
        int  rst = 0 ;
        while (n != 0) {
       	 n = n & (n - 1);
       	 rst++;
        }
        return rst == 3 ;
   }

- Scott April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Good solution, using the Kerninghan's algorithm.

- Killedsteel April 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

By the way, another solution is to do this via a lookup table (you'd have to ask the interviewer how frequently this operation is to be performed though). If frequency and usage of this operation is high, it makes sense to keep in memory all the 8-choose-3 combinations of setting 3 bits from 8. We can then simply do a lookup to return true/false.

- Killedsteel April 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If there are more than 3 set bits, it is better to stop earlier (don't check all bits)

boolean hasThreeSetBits(int i) {
	for (int k = 0; k < 3; k++) {
		if (i == 0)
			return false;
		i = i & (i - 1);
	}
	return i == 0;
}

- Max April 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

This is the second post as the first one does not seem to appear

You can also solve this using the "Hamming Weight" way (check wikipedia)

const char m1  = 0x55; //binary: 0101...
const char m2  = 0x33; //binary: 00110011..
const char m4  = 0x0f; //binary:  4 zeros,  4 ones ...

bool bitCount3(char x) {
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    return x == 3;
}

- zsalloum April 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

bool fun(int t) {

int num=0;
int one=1;

while (t!=0) {
one=one&t;

if (one==1)
num++;

t=t>>1;
one=1;
}

if (num==3)
return true;
else
return false;

}

- BMW April 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static final int countBits(final byte input, final int lookupBit) {
		int counter = 0;

		int tmpInput = input;
		if (tmpInput != 0) {
			while (tmpInput != 0) {
				if ((tmpInput & lookupBit) == lookupBit) {
					counter++;
				}
				tmpInput = tmpInput >>> 1;
			}
		} else {
			if (lookupBit == 0) {
				counter++;
			}
		}
		return counter;
	}

	public static final boolean checkIfByteHas3OneBits(final byte input) {
		final int oneBits = countBits(input, 1);
		return oneBits == 3;
	}

- Scavi April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int CountBits(byte input)
{
	int result = 0;
	while(input != 0)
	{
		result += input%2;
		input == input >> 1;
	}

	return result;
}

public static IsByte3Bits(byte input)
{
	return CountBits(byte) == 3;
}

- Nelson Perez April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CheckByteAtLeastNBitsSetToX {

public static void main(String[] args) {
	System.out.println(hasAtLeastNBitsSetToX((byte)7, 3, true));
}


public static boolean hasAtLeastNBitsSetToX(byte n, int k, boolean isSet) {
  int n1 = n;
  int countOnes = 0, countZeros = 0;
  while (n1 > 0) {
   if ((n1 & 1) > 0) {
     countOnes++;
   } else {
	 countZeros++;
   }      
   n1 = n1 >> 1;
  }
  
  return isSet? (countOnes >= k) : (countZeros >= k);
}

}

- guilhebl April 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool fun(int t) {

int num=0;
int one=1;

while (t!=0) {
one=one&t;

if (one==1)
num++;

t=t>>1;
one=1;
}

if (num==3)
return true;
else
return false;

}

- ehsan April 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool is3BitsOn( unsigned char oneByte)
{
int bitOnCount = 0;
for(int i = 0; i < 8; ++i)
{
if(oneByte & 0x0001 << i)
{
bitOnCount++;
}
}
return bitOnCount == 3;
}

- vincent April 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool check_bits(char byte)
{
   int count=0;
   while(byte > 0)
   {
	   if(byte & 0x1)
	   {
			count++;
	   }

	   byte >>= 1;
   }

   return (count==3);
}

- Alex April 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

In Java, the simplest way is to use Integer.bitCount(int i):

boolean hasThreeSetBits2(int i) {
	return Integer.bitCount(i) == 3;
}

- Max April 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This fails for any negative number, since the method converts the number to an int. The original question specified a byte. This will count the bits in an integer.

- Deege April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote
Not sure KR method with overflow due to n* n-1 public boolean validateByte(byte n) {{{ int rst = 0; while (n != 0) {{{ n /=2; rst += n % 2; }}} return rst ==3; }}} - Ankush Bindlish April 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar solution as others but shifts a checking int left rather than the input number right.

boolean hasThreeSetBits(int n) {
    int check = 1;
    int count = 0;

    while (check < n) {
        if (n & check == 1) {
            count++;
            if (count > 3) {
                return false;
            }
        }
        check <<= 1;
    }

    return count == 3;
}

- JW April 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you need a fast search, simply make an array of 256 booleans.
An index will be the input, and the boolean value will be an output.

- sergey.a.kabanov April 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int check3bit(unsigned char b) {
	int sum=0;
	for(int i=0; i<8; i++)
		sum += (b>>i & 0x01);
	return sum==3;
}

- Anil April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static bool HasThreeBit(byte value)
  {
    byte compare = 1;
    int nbBit = 0;

    for (int i=0; i < 8; i++) {
      if((value & compare)> 0)
          nbBit++;
      compare <<= 1;
    }
    return nbBit == 3;
  }

- ardumez April 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a hash_map of all 256 possible values for 1 byte and this returns the key values as the number of bits set.
For example: hash_map[0x7] returns 3 and hash_map[0x2] return 1.

bool num_bits_set_3(uint8 input)
{
    return ((bool)(hash_map[input] == 3));
}

- Sravan April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool Bit_Check(int a){
    int count = 0, b;
    while(a != 0){
        b = a % 2;
        a = a/2;
        if(b == 1)
            count++;
        if(count == 3)
            return true;
    }
    return false;

- Chenna April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean checkBits(byte n) {
		int countOnes = 0;
		for (int i = n; i != 0; i = i >> 1) {
			countOnes += (i & 1);
		}
		return countOnes == 3;
	}

- romina May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Function to get no of set bits in binary
   representation of passed binary no. */
int countSetBits(int n)
{
    unsigned int count = 0;
    while (n)
    {
      n &= (n-1) ;
      count++;
    }
    return count;
}

Now, we can simply terminate after 3rd iteration (if n is still != 0) & declare the result.

Maximum complexity = 3 operations.

/* Function to check if it has 3 bits */
boolean has3Bits(int n)
{
    unsigned int count = 0;
    while (n)
    {
      if(count == 3) return false; //more than 3 bits

      n &= (n-1) ;
      count++;      
    }

    if(count == 3)    return true;
    else    return false;  //less than 3 bits.
}

- X May 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

very simple logic!!!

add all bits if result is equal to 111 then its correct else it's wrong.

- yash mehta June 07, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More