3 ms·

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

by 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.

by baddox 9y ago

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.