Amazon Interview Question: Asked to implement a function... | Glassdoor

## Interview Question

Software Development Engineer In Test Interview(Student Candidate) Seattle, WA

# Asked to implement a function that takes an integer and

returns whether or not the number had an odd or even number of 1 bits.
Tags:

2

It started out with an ambiguous set-up so the first thing that needed to be figured out was what kind of number to be taken in. How many bits this value was. I was told to assume it was 32 bits. I mentioned that the number may be in 2's complement, I was told to only expect unsigned integers. The solution is pretty straight forward, it only requires a for loop that counts from 0 to 31 and checks whether the integer masked with 1 is equal to 1. If it is, add one to the accumulator and shift a bit to the right. Then I was told to extend this function to work for an n bit integer. With some hints I figured out that log base 2 of a number gave you the maximum number of bits it would take to store that number so simply replace the loop that went from 0 to 31 with a loop that goes from 0 to log_2(n).

Interview Candidate on Jan 27, 2012
1

If the task is only for positive numbers, then my solution would be:

bool is_odd_set_bits(unsigned number)
{
bool result = false;
int n = number;

do
{
result |= ((n % 2) == 1);
n /= 2;
}
while ((n / 2) != 0);

return result;
}

Tim on Jan 31, 2012
1

needajob on Feb 1, 2012
1

mod and div operators are good, but you could set yourself apart by using a more efficient algorithm. In terms of big O, it will be the same, but it will have a higher throughput since the operations are slightly faster.

&gt;
bool is_odd_set_bits(unsigned number)
{
bool result = false;
int n = number;

while(n != 0)
{
result |= ((n &amp; 0x01) == 1);
n &gt;&gt; 1;
}

return result;
}

masking is faster than a mod operator, and bit shifting is faster than divisions

PC on Feb 8, 2012
0

i was trying this in java and found kinda small bug... so we should return false if the number is 3 which is 0000000011.
I guess changing the line to:
result ^= ((n &amp; 0x01) == 1);
will do the job...

Anonymous on Apr 30, 2012
0

PC, your solution is incorrect. It will always return true if the number has at least one set bit.

Pavel on May 25, 2012