> There's an array of 10,000 16-bit values, how do you count the bits most efficiently?
I would have said that I would multiply 10000 by 16. Oh well, no Google job for me I suppose.
I would have said that I would multiply 10000 by 16. Oh well, no Google job for me I suppose.
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.
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;
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.