Hacker News Reader

Comment by gamegoblin | Hacker News Reader

For a low level programming backend job:

Tell me everything you know about the hash table data structure.

Plenty of Staff level applicants don’t know anything about it.

There are 3 tiers of answer:

1) Don't know what a hash table is, when to use one, etc. Have never had a candidate in this category this do well in the rest of the interview, even for totally unrelated tasks like distributed system design.

2) Know it's a key-value store, know it's "fast". Some candidates whose main experience is in frontend dev get to this point, and then demonstrate other ability in the rest of the interview and get hired.

3) Rattle off that it's O(1) amortized, might be O(N) in the resize case, chaining vs linear vs quadratic probing vs other clever methods like cuckoo hashing, discuss how those methods effect cache behavior, etc. These candidates typically crush the rest of the interview effortlessly, even totally unrelated tasks like distributed system design.

View on HN

When I was in college, I had recently implemented hash tables in a data structures class and was interviewing for internships. I gave a detailed answer like (3). The interviewer told me that it was the best answer he’d received for that question.

Now I have several years of experience and am a much more effective engineer. I don’t remember many of the implementation details of a hash table anymore, but I still know how roughly how fast the operations are.

I guess I wouldn’t be applying for “low level programming” jobs, so the expectations are different. Still, I think I’d be better at it than younger-me who just learned data structures.

This^. OP is basically just filtering for people who have experience building hash tables.

For people with recent experience building hash tables. What sticks over the years is how you work with them and where they are a good solution to a problem. The more experience you have in using them, the less likely you are to remember how to build them, because that information was never used and got pushed out of memory by all of the other things an experienced developer needs to remember.

They did say "low level programming backend job". At least a large subset of what they mentioned should be common knowledge then.

You can get into bucket 2 if you just use hash tables and know the most basic information about their use. Plenty of candidates were in this bucket and passed the rest of the interview.

I still gave the rest of the non-hash table interview to every candidate. What I'm saying what the hash table question was a tremendous predictor of candidate success in every other aspect of the interview. System design, algorithms, problem solving, etc.

Candidates that didn't know anything about a hash table, even just the most basic idea of "fast insert/lookup/delete key-value datastructure", almost universally failed almost every aspect of the rest of the interview.

Candidates that know the basics could go either way.

Candidates that know all the details almost universally crushed every other aspect, including very unrelated things like distributed system design.

Not even that.

There are people out there who have built hash tables, who don't even know what they've built is called a hash table by educated folks. I know this, because I formerly happened to have worked with such a guy, after needing to change some of his code and discussing it with him.

That reminds me of an interview where I was asked about something about "a module", to which I responded that I needed some clarification, and rattling off like 4 different uses of the word, only to be meant by a blank stare because supposedly I was to guess whatever specific technical term in $techstack the person was referring to.

It sounds like you'd fall into bucket 2, and would probably pass the rest of the interview on other merits.

This low level programming job, we were implementing filesystems from scratch. Very, very data-structure heavy.

Reply on news.ycombinator.com