On a great interview question
This is not a great interview question. It’s not even a good interview question. It <i>barely</i> evaluates any technical abilities and it ignores most technical abilities that matter.<p>This question could be improved as follows:<p>* present the naive solution. Explain that this is a PR that was submitted in 20 minutes by our new intern from Waterloo. Ask them to help improve it.<p>* suggest to them the intern’s argument why the lookup is O(1) and explain that it’s actually O(n). Ask them to write a PR comment to break the news to the intern.<p>* explain the optimal solution with tries. Ask what happens if the vocabulary is big enough—and the prod environment is resource constrained—so that the trie is rarely in memory when the function is called. How would the trie solution compare to a binary search through a length normalized list of words?<p>This kind of question is barely useful to interview new hires—when you still may have basic questions about how much undergrad material “stuck”. Within a few years when they hit full-performance level you should care much less about this kind of question and much more about “higher order” thinking about engineering.<p>How do you communicate bad news? How do you identify, communicate, and mitigate risk? How do you plan large tasks at at appropriate level without over engineering the solution? What questions should you ask at different project stages to capture the right requirements, anticipate issues, and successfully execute over time?<p>But whatever, I’m sure you get lots of signal out of repeating “a hash table lookup is O(1)” “nuh uh” on loop for 10 years. :eyeroll: