[nanidin]

I have a traditional Computer Science background and I'm still intimidated to even apply to Google. I got out of bigCo Software Engineering in part because I wasn't interested in putting myself through the wringer of whiteboarding memorized solutions.

I'm also the guy that found low hanging fruit in a huge codebase to replace things like frequent linear array lookups with hash table lookups for 10x+ speed improvements in the build process. This is IMO precisely the type of capability that "Oh, that's O(n^2), surely we can do better. Is there any way to do this in O(1)?" is designed to tease out in the interview process. I did it! In a build process effecting 1000+ engineers, used to build for millions of shipped units! But talking about this in an interview makes eyes gloss over as we prepare to move on to sort algorithm trivia, how would I design search, or doubly linked list implementations.

[eru]

See https://sockpuppet.org/blog/2015/03/06/the-hiring-post/

[ant6n]

But you know, hash tables have O(n) access...

[eru]

Some implementations have O(n) access in the worst case.

Often people are interested in something like the 99.9999%ile case. And, of course, you can design hash tables with better worst case behaviour.

It's almost trivial to get a hash table with O(log n) worst case access: when you have a collision, just resolve it with a tree instead of a linked list.

With some more fancy math, you can also get O(1) amortized worst case behaviour with arbitrarily high probability that doesn't depend on your input data.

[motioncuty]

And this is where interviewing gets hard. Are we really going to not hire someone because hash table is O(n) in the worst case but O(1) on average. It seems like half the time there isnt a match, the interviewer is just as wrong as the candidate, and they are looking for someone who knows the same info as them, even if its half baked.