Hacker News Reader

Comment by baddox | Hacker News Reader

I love interview horror stories! In my most recent job search, which was early this year, I debated with one interviewer whether checking for key existence in a hash was a constant time operation. I insisted it was, and the interviewer insisted otherwise with the same amount of conviction. That was just a small portion of an all-day onsite interview. After leaving, I was told they were looking for a more senior candidate. I was not upset.

View on HN

Could just be a terminology mismatch. Checking for hash existence should always be constant, but checking for key existence is generally only amortized constant (that is to say, not constant across all lookups) - he may have wanted you to talk about addressing schemes and degradation at high load factors?

There was no subtle argument. It only came up because I was on the whiteboard solving some simple word game that involved matching user input against a list of valid words (e.g. the Scrabble dictionary). When asked to explain the running time of the various operations, I said that we can store the dictionary in, well, a dictionary, and checking whether the user input is a valid word will be a constant time operation. The interviewer insisted, with no subtle argument about amortization or collisions or addressing, that this was in fact a linear time operation.

So likely thinking of it in terms of checking a tree based on characters instead of hashes of full words. Which is more viable would likely depend on what kind of memory constraints and dictionary size was being considered. Also very implementation dependent, what's the size of the hashes generated?

Edit: curiosity got me looking at this for Python, with an answer of "it depends, and both have correct aspects" based on Python's implementation [1]. The hashing varies by string length, the lookup is fixed unless there's a collision and probing, probing will be minimized by growing the dictionary as items are added. In any case, better than O(n) but worse than O(1) and with some possible slowdowns during loading unless you can set an expected final size during initialization.

Edit again: since I brought it up, turns out initialization doesn't really matter, resizing is not a speed factor. Relevant discussion starts from https://stackoverflow.com/questions/1298636/how-to-set-initi...

[1] http://www.laurentluce.com/posts/python-dictionary-implement...

It's also possible the interviewer meant linear time as a function of the length of the word, which would be true. Regardless, not being able to express this clearly is a sign of a poor interviewer which unfortunately the candidate takes the hit for.

That was certainly not the case. Multiple times the interviewer "explained" that with my approach you have to run through every entry in the word list which is linear time. My guess is that the interviewer wanted me to mention a prefix tree of some type, and was completely blind to any other approach.

Indeed, my best guess is that the interviewer had a mental check list and simply wanted me to say "prefix tree" or "trie" or similar. I suspect the debate over running time was just the interviewer's attempt to get me to say the magic word he wanted to hear. I also suspect the interviewer did not know much about hash tables or tries, or was so nervous and misguided about interviewing that the information was not readily recallable.

> checking for key existence is generally only amortized constant (that is to say, not constant across all lookups)

What you just described is "average" not "amortized". Amortized does not mean "across a set of representative inputs", it means "through time, even if given the same input repeatedly".

Amortized complexity is tricky sometimes. For instance, in a data structure storing a binary integer and allowing an increment operation, the number of bits flipped is amortized O(1). The same is true if the only operation is decrement. Neither is true if you have both increment and decrement!

Another example: you can change the accounting to make things amortized lower cost. For instance, a heap (aka implicit priority queue) can be said to have O(1) deleteMin by simply ascribing an extra O(log n) cost to each insert. In fact, you can say deleteMin has O(0) cost! An example of this being done in the literature is https://arxiv.org/abs/0903.4130, "Pairing Heaps with Costless Meld", by Amr Elmasry.

My favourite was an interview (in Java), where the interviewer said I needed to process some data (something abstract like a "record") and that I could assume I get my data in a "var". I asked what sort of data structure the variable held. He said "It's a var. You know what a var is, right?"

So many problems...

It can also depend on whether you count the O(k) time needed to hash a string of length k.

Wouldn't that argument be easily settled by discussing the implementation of a hash table?

I discussed it briefly. My interviewer was unpersuaded, and the other interviewer in the room (who wasn't performing this interview) suggested we just move on. I believe the unconvinced interviewer was simply a very junior developer and an even more junior interviewer. He seemed quite nervous.

One of the worst interviews I've had the interviewer was not only similarly incorrect, but then afterwards proceeded to try to give me advice on interviewing skills, and how I should've "taken his hint" and been "more amenable to other answers". I probably would've been open to alternate answers if they were, y'know, factually correct.

Thinking you are awesome because you know the answer to a question you have prepared for and asked many times, is one of my minor irritant

If you think that's bad, I was this guy[1].

tl;dr:

1) Interviewer insists that an operation must be n^2 "because it has a nested loop" even though the nested loops are only iterating over their own subset of the master string.

2) Interviewer refuses literally any test that would help decide which of us is right.

3) Interviewer turns out to not even understand the concept of resolving disagreements by appealing to agreed-upon facts, insisting that he would only be convinced by the absence of a nested loop (i.e. talking about some other algorithm).

4) Interviewer is five-year backend lead.

5) Interviewer vetoes me from the rest of the process purely because of that disagreement.

6) Because I thought I was going insane, I implemented it at home and ran the problem with different sizes and the run time with up as O(n) like clockwork.

[1] It's okay, I'm fine with people knowning and have outed myself elsewhere: https://news.ycombinator.com/item?id=6070001

> Interviewer turns out to not even understand the concept of resolving disagreements by appealing to agreed-upon facts

That's a wonderful description of an attitude I have encountered many times.

Reply on news.ycombinator.com