←back to thread

Google's “Director of Engineering” Hiring Test

(www.gwan.com)
1764 points fatihky | 4 comments | 13 Oct 16 15:15 UTC | HN request time: 0.925s | source
Show context
sonoffett ◴[13 Oct 16 15:58 UTC] No.12701639[source]▶
quicksort is O(n^2) which is definitely not the "best big-O" for sorting.
replies(4): >>12701670 #>>12701718 #>>12701729 #>>12701867 #
1. sonoffett ◴[13 Oct 16 16:03 UTC] No.12701670[source]▶
"how do you count the bits most efficiently?"

What does this even mean?

replies(2): >>12701753 #>>12701756 #
2. UK-AL ◴[13 Oct 16 16:12 UTC] No.12701753[source]▶
What i think he means is counting the amount of set(1) bits in the array,
replies(1): >>12701768 #
3. dekhn ◴[13 Oct 16 16:12 UTC] No.12701756[source]▶
If you have a collection of data, and you want to know the number of 1 bits, and you want to do it with a minimum of resources... what is the process?

For example, standard bit-shifting and masking the lowest bit to set a counter is one way to do this. Possibly there are other, faster ways, such as using a lookup table (a byte or more can be "counted" at a time). Of course, because so many people were doing this, intel added a popcnt instruction which probably is more efficient (faster) than either of the above, at the expense of more CPU real estate, heat, etc.

Turns out counting 1 bits in a dataset is a super-important problem that shows up in a lot of situations.

4. sonoffett ◴[13 Oct 16 16:13 UTC] No.12701768[source]▶
Thanks, the question makes more sense now :)