Hacker News Reader

Comment by tptacek | Hacker News Reader

I agree with this sentiment wholeheartedly but bounds on balanced binary trees are worth knowing (like lookup, it's log n), since that fact is one of just two reasons you'd ordinarily ever use a tree.

However, I will offer you some Interview Candidate Self Defense, which I'll repeat from something I yelled on Twitter a few weeks ago:

If interviewers ask you about bounds for data structures, pick a fight with them over hash table complexity. If they believe it's O(1), argue it's worst case O(n). If they want you to say worst case O(n), argue that it's in the real world always O(1). It doesn't matter which is right, because these kinds of questions aren't about technology, they're about status signaling. Be the alpha nerd!

As a bonus: interviewers are evaluating you for X-factors like "confidence". You know who never got dinged in an interview for lacking "confidence"? The person who yelled at the interviewer about hash table complexity.

View on HN

Adopt an aggressive posture. Maintain eye contact and repeatedly say "amortized complexity".

The Illustrated Tech Interview Survival Guide would like a word with you.

If they say average case O(1), worst case O(n), hit them with them with O(log n / loglog n) with high probability from a simple balls-into-bins type argument.

Could you expand on the balls-into-bins argument here? It's not quite obvious to me, but I'd really like to understand.

Items are balls, slots in your table are bins. Hash functions are assumed to distribute them randomly (uniformly). See also the Wikipedia article on Balls-into-Bins.

https://en.wikipedia.org/wiki/Balls_into_bins

This reference from the wiki is good http://www14.in.tum.de/personen/raab/publ/balls.pdf

I assume you mean this tongue-in-cheek, but someone yelling at me in an interview is probably not going to score well on the "Do I want to work with them?" X-factor.

Of course, a well-informed discussion of hash table complexity would be pretty fun to hear from a candidate. It's always great when I learn something new in an interview.

I'm like 60% tongue in cheek, because the reality is, for every interviewer who will filter you for being too aggressive, two more will filter you for lack of confidence.

I have never once filtered someone for lacking confidence. I have never seen someone filtered for lack of confidence by any panel I've been on or any panel I was the hiring manager for. At this point in my career I have interviewed ~1000+ engineers.

I think you're interviewing with the wrong people, or at the wrong places. Way too many people treat interviewing as a way of demonstrating intelligence via computer science trivial pursuit. 5 minutes with Google will demolish 99% of the questions you might ask if all you care about is getting correct code on the board. The interesting part is the process and discussion the code creates, not whether or not they know the secret handshake.

That's nice, but I have literally read interview feedback from very smart interviewers at multiple companies that vetoed candidates because "they didn't appear confident". This isn't something I'm making up: it's a real problem.

I think we can both agree that interviewing is overdue for a radical reboot. Silicon Valley, disrupt interviews, please!

That said, there are places that don't interview the way you describe. I'm equally sure there are places that do (I vividly remember my Dropbox interview). My hope has always been that Darwin's Law will apply to such places over the long run, but instead I think what actually happens is that as these organizations grow the interview process just ends up being a diluted version of the same BS, which translates into "lowering the bar." Nevermind that your bar was curvier than Lombard Street.

"Silicon Valley, disrupt interviews, please!"

They did and that's the problem ;)

This is mostly good advice -- it's worth knowing both worst case and amortized average time -- but plenty of interviewers will filter you if you're being an aggressive asshole, even if you're right about facts.

Make sure you're considering what the workday environment is like (something you can usually tell from the prep materials or discussions with recruiters) and acting the way you think you'd act in that environment.

>If they believe it's O(1), argue it's worst case O(n)

In the case that all your keys have the same hash, right?

Right!

It seems to me this would entirely depend on the implementation and how collisions are handled.

Buckets. :)

In Java 8, collisions in Maps are stored in a tree structure so worst case is O(log n)

Is it a balanced tree? If not, worst case could still be O(n).

Haha, that would be an odd set of data indeed. I have no idea how they implement it but I hope I have made a point(I feel I have). I wouldn't be too impressed with an interviewer or interviewee arguing one side or the other about the complexity of "unspecified hashmap implementation".

Too clever by half.

Reply on news.ycombinator.com