5 ms·

Could just be a terminology mismatch. Checking for hash existence should always be constant, but checking for key existence is generally only amortized constant

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?

baddox 9y ago
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.
- fencepost 9y ago
  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-initial-size-for-a-dictionary-in-python https://stackoverflow.com/questions/1298636/how-to-set-initi... [1] http://www.laurentluce.com/posts/python-dictionary-implementation/ http://www.laurentluce.com/posts/python-dictionary-implement...
  - kevmo314 9y ago
    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.
    - baddox 9y ago
      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.
  - baddox 9y ago
    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.
jbapple 9y ago
> 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 https://arxiv.org/abs/0903.4130, "Pairing Heaps with Costless Meld", by Amr Elmasry.

baddox 9y ago

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.

fencepost 9y ago
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-initial-size-for-a-dictionary-in-python https://stackoverflow.com/questions/1298636/how-to-set-initi... [1] http://www.laurentluce.com/posts/python-dictionary-implementation/ http://www.laurentluce.com/posts/python-dictionary-implement...
- kevmo314 9y ago
  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.
  - baddox 9y ago
    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.
- baddox 9y ago
  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.

jbapple 9y ago

> 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 https://arxiv.org/abs/0903.4130, "Pairing Heaps with Costless Meld", by Amr Elmasry.