I find that the solution to a lot of these trick interview questions is to use a hash table or some kind of a look up table. Even the famous google mock interview video uses a hash table in the solution.

The solution to this question is to use a 256bit lookup table. You'd need to precompute the lookup table that will give you the bit count of every possible bit combination in a byte. Then traverse your 10,000 long array, use your lookup table to count the bits and add them to your total.

Assuming that they want the number of 1 bits (the question asked for the number of bits, not the number of 1 bits--hence my answer), it is not obvious to me that a lookup table is the fastest.

Given an unsigned 32-bit value, v, this well-known bit hack [1] counts the number of 1 bits:

  v = v - ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  count = ((v + (v >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24;

If you can treat the 10000 16-bit values as 5000 32-bit values, applying the above 5000 times might be as fast or faster than applying the table lookup method to 20000 bytes. It will depend on precise details of the particular computer on which it is run.

[1] http://graphics.stanford.edu/~seander/bithacks.html

Nope, hardware is better. Throw popcount at it, in parallel. ispc will help you with the parallel bit if your compiler cannot autovectorize good enough.

Hilarious and technically correct!

As others have pointed out, this is just a filter for Google to see who wants the job the most and is willing to jump through the most hoops.

Google misses a lot of good candidates but the ones they get are good so they do not have to care about the broken process.

One could even say that this broken hiring process encourages the customer-averse CS automation nightmare at most Google products.

Hypothesis: Someone who experiences a hazing ritual to get a job at Google is less likely to worry about being nice to customers and will try to automate all customer facing interactions.

If one was going to be hired to work on cloud API or some enterprise tool, not sure how this low question would qualify someone as a better software engineer.