> suggest to them the intern’s argument why the lookup is O(1) and explain that it’s actually O(n).
I think any discussion of complexity for this problem is misguided.
I mean, it's fine to talk about a hash lookup being o(n) for pseudocode in some hypothetical context. But if you're talking about actual code that you intend to run in Python or JS or whatever, it doesn't make sense - are the strings interned or not? When your language hashes the key of a dictionary lookup, does it cache the result? If you're using a JITTed language, won't any native o(n) hash lookups vanish in comparison to your non-native o(n) for-loop?
On top of all of which - why are we even talking about o(n) complexity for an n that cannot grow? If we're given a fixed dictionary then we can ignore any substring longer than its largest element, so the "n" for hash lookups is not the size of the original input - which is the n we realistically care about!
Basically, once TFA mentions complexity I feel like the only correct answer is to say "this isn't a situation where complexity analysis would be useful - we should benchmark the code".
Your comment is exactly the kind of thing I’d like to see a candidate simulate explaining to an enthusiastic, overachieving intern. Is the candidate helpful? Are they toxic? “Explain the the intern” implies a hierarchy imbalance—does that make them rude or patronizing?
All of these are useful signals for a hiring decision. Much more than quibbling about big-O of hash table lookups.
> He was asking about the complexity in relation to the size of the input string,
But you don't try checking if the entire string is in the dictionary regardless of n - you only ever check if it's in the dictionary if it's shorter than X+1 where X is the longest string in the dictionary. As the input string size grows, the dictionary lookups are capped.
The underlying issue here is that TFA doesn't describe having a discussion about the complexity.
If the author asked about complexity as an open-ended question with no fixed answer, that would be a very reasonable way to hear how the candidate thinks about algorithms. But TFA makes it clear that the author treats it as a gotcha question - he expects candidates to say o(n) and then pushes them to give the answer he wants. That's not a great approach, even if the interviewer's preferred answer is unambiguously correct - and here it's not.
I think any discussion of complexity for this problem is misguided.
I mean, it's fine to talk about a hash lookup being o(n) for pseudocode in some hypothetical context. But if you're talking about actual code that you intend to run in Python or JS or whatever, it doesn't make sense - are the strings interned or not? When your language hashes the key of a dictionary lookup, does it cache the result? If you're using a JITTed language, won't any native o(n) hash lookups vanish in comparison to your non-native o(n) for-loop?
On top of all of which - why are we even talking about o(n) complexity for an n that cannot grow? If we're given a fixed dictionary then we can ignore any substring longer than its largest element, so the "n" for hash lookups is not the size of the original input - which is the n we realistically care about!
Basically, once TFA mentions complexity I feel like the only correct answer is to say "this isn't a situation where complexity analysis would be useful - we should benchmark the code".