No, they're not asking for details of hash table implementation. The main goal is to see if you can scale the algorithm, for which they're the real experts. The hash table discussion is a mere diversion. The "expected" progression of the particular discussion is: 1. hash table implementation (simplest map container) when you have enough RAM to see if the candidate gets cs basics. 2. sort | uniq -c when you have enough disks on a single node to see if the candidate has experience with non-trivial amount of data (larger than RAM.) and understanding of modern disk performance characteristics (random vs sequential I/O) 3. map-reduce on multiple nodes for the entire internet; see if the candiate has experience and understandings with distributed computing. So the author didn't make very far. His attitude and mindset were also getting in the way of interviewers' steering the interview. It's a classic case of impedance mismatch in interviews.
Re:My toughest job-interview question ever
by derefr on Tuesday May 12, 2009 @06:30AM
(#605156)
He said the interviewer had never heard of cuckoo hashing. That's a slightly different matter than a "not having instant recall", especially for someone asking questions about how to implement hashtables in the first place (they should have looked at the relevant reference before going in to do the interview, as they were obviously following a very fixed format, instead of letting the discussion range.)
[ Parent
| on HN ]
Cuckoo hashing is a relatively new but underperforming hashing scheme due to the fact it's not cache friendly for modern processors: "despite its constant worst-case look-up cost, the bucketized cuckoo hash table was demonstrated to be the slowest hash table, far inferior to both the chained and array hash tables."