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:
technical, c, bit-masking
Answer

Interview Answer

6 Answers

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.

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

    while(n != 0)
    {
        result |= ((n & 0x01) == 1);
        n >> 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 & 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.