Google's “Director of Engineering” Hiring Test

quicksort is O(n^2) which is definitely not the "best big-O" for sorting.

"how do you count the bits most efficiently?"

What does this even mean?

Its worst case is O(n^2) sure, so heap sort would be better if you know that your data would hit the worst case scenario of quick sort every time.

quicksort is O(nlogn) average case, and O(n2) on already sorted arrays.

What i think he means is counting the amount of set(1) bits in the array,

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.

Thanks, the question makes more sense now :)

Quicksort is O(n log n) average and O(n^2) worst case. Heapsort is O(n log n) for both average and worst case.

Just a nitpick: There are versions of quicksort that perform well, O(n*log n), on already sorted data. But there is always some worst case scenario where it can be O(n^2).