## 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 ;
}``````

Comment hidden because of low score. Click to expand.
2

Good solution, using the Kerninghan's algorithm.

Comment hidden because of low score. Click to expand.
0

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.

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;
}``````

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;
}``````

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;

}

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;
}``````

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;
}``````

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);
}

}``````

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;

}

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;
}

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);
}``````

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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

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; }}}
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;
}``````

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.

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;
}``````

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;
}``````

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));
}``````

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;``````

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;
}``````

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.
}``````

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.

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.

### 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.