3 ms·
He was asking about the complexity in relation to the size of the input string, not dictionary size.
by throwawaylinux 3y ago
He was asking about the complexity in relation to the size of the input string, not dictionary size.
- deleted 3y ago[deleted]
- IanCal 3y ago> 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.
- throwawaylinux 3y agoAnd I'm sure he would have accepted that in a discussion about the complexity.
- fenomas 3y agoThe 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.
- throwawaylinux 3y agoI don't think that's the underlying issue. TFA sounded quite open about getting into deeper discussions and side topics as they go.
- deleted 3y ago[deleted]