Re:Google's “Director of Engineering” Hiring Test
by spott on Thursday October 13, 2016 @02:35PM
(#12702976)
Who's answer is wrong? Cause no-one suggested a 16bit lookup table.
His answer was to look at 64 bits at a time and do a [0] Kernighan style count. The "correct" answer was an 8-bit lookup table. Which is right is going to be highly dependent on the data and the architecture you are using.
[0] http://stackoverflow.com/questions/12380478/bits-counting-al...
Re:Google's “Director of Engineering” Hiring Test
by powera on Thursday October 13, 2016 @02:51PM
(#12703102)
You're correct, I misread what he said the recruiter's answer was.
Re:Google's “Director of Engineering” Hiring Test
by rayiner on Thursday October 13, 2016 @02:19PM
(#12702852)
Do you recall the question? Site's down. I recall thinking the right answer was to use POPCNT but maybe I'm misremembering the question.
Re:Google's “Director of Engineering” Hiring Test
by powera on Thursday October 13, 2016 @02:57PM
(#12703137)
The question was "how do you do bit-counting of a bunch of numbers". The two canonical answers are "lookup table" and "using bit shifts and multiplying by magic numbers".
The fact that there's a machine instruction for it does makes it a bad question.
Re:Google's “Director of Engineering” Hiring Test
by mitchty on Thursday October 13, 2016 @03:06PM
(#12703196)
Honestly I would have said popcnt as well. Lookup table or bit shifts when I can have the cpu count the 1's? I guess i'd need to benchmark it to be sure. Either way I can't say its a good question.
Re:Google's “Director of Engineering” Hiring Test
by gcp on Thursday October 13, 2016 @04:21PM
(#12703725)
Popcnt isn't particularly well optimized in most micro-architectural implementations.
Re:Google's “Director of Engineering” Hiring Test
by mitchty on Thursday October 13, 2016 @05:31PM
(#12704215)
Looks that way with a quick test. But it looks like there may be a better way with SSE3 PSHUFB:
http://wm.ite.pl/articles/sse-popcount.html
Re:Google's “Director of Engineering” Hiring Test
by rayiner on Thursday October 13, 2016 @05:45PM
(#12704321)
Is it? It looks like on most recent Intel CPUs, it's 3 cycle latency, 1 cycle throughput on a 64-bit register. A 8-bit LUT solution is going to less than 16-bits per cycle on any recent Intel/AMD CPU (maximum of two load ports).
Re:Google's “Director of Engineering” Hiring Test
by gcp on Thursday October 13, 2016 @06:21PM
(#12704597)
Hmm, much better than I remember. I guess this goes a long way to explain why this wasn't always seen in practice: http://danluu.com/assembly-intrinsics/
Based on his LinkedIn profile, I don't think anyone at Google would have thought of him as a "director of engineering". Being an "R&D director" at some unknown company at 24 is entirely un-comparable to a director at Google, and since then he's worked at his own very small company. He was probably a candidate for Senior SRE.