4 ms·

Yeah, sorry, I don't think I'm following your argument. When you compute hash keys of a string, of course you want to read the whole string at least once, so t

Yeah, sorry, I don't think I'm following your argument. When you compute hash keys of a string, of course you want to read the whole string at least once, so the time complexity is at least O(N) (where N is the length of the string) - sure it's easy to overlook, but once explained there's not really much to disagree. It's not like the interviewer is asking a matter of opinion and punishing those who have different viewpoints. Also, once you used the same problem half a dozen times in interviews, you no longer get any "warm and fuzzy" feelings for having to explain something which is now blindingly obvious to you: if anything, you'll give higher scores to candidates to whom you don't have to explain such things. Of course, if you are a candidate and (hypothetically) your response is "Actually it can be less than O(N), because a hash function does not have to read the entire string, and I know how it works because I've been dealing with string hash functions for years in my professional career," then by all means, fire away, I'm pretty sure any reasonable interviewer would consider it as a big plus sign.

jameshart 4y ago
It’s O(n) in an n that doesn’t matter. The length of that word does not grow arbitrarily long, causing the asymptotic behavior of your algorithm to dominate. Because it’s a word. In the case of ‘is this word of length n the result of concatenation two English words’, the time complexity as n approaches infinity is constant, because once you get past floccinaucinihipilificationantidisestablishmentarianism, any longer word than that you can just return ‘false’ immediately.
- krackers 4y ago
  Right, for all practical purposes if the reader assumes the words are from the English language, you can assume that comparisons will be constant (both from the pedantic CS perspective since words are bounded in length, and also from a practical perspective since the bound is small, and with SIMD can be done fast enough for most words). See also responses from https://news.ycombinator.com/item?id=35550842 https://news.ycombinator.com/item?id=35550842 and https://news.ycombinator.com/item?id=35551114 https://news.ycombinator.com/item?id=35551114 which say the same better than I could. It feels really disingenuous when interview questions start off posing a seemingly innocent problem where the intuitive and practical answer is usually the one that'd you go for if you wanted to implement this in the real-world, then as soon as you answer the interviewer turns around and throws a hidden assumption at you. You could argue that the point of the interview is to have the candidate suss out these things, but it's usually a one-way discussion where you're not allowed to even question if the assumptions make sense in the real-world (which is what you ultimately care about). And if the words are truly big enough to be an issue then you better start being rigorous and benchmarking different approaches rather than just handwaving big-o. Ultimately when you get down to it, the whole point seems to see if the interviewee can be led down the pre-determined golden path, even if the path is only fools gold.
- yongjik 4y ago
  I see, yes I think you do raise a very good point, but on the other hand, the issue could be quickly resolved by talking about it. Any good interviewer would say something like "Ah yes that's a very good point, I forgot to consider the implication of the English vocabulary. However, for the sake of this interview, let's assume the 'vocabulary' is made of strings that can be arbitrarily long. Does that change your answer?" After all, if we assume that all words are at most, say, 50 characters long, then there's no asymptotic complexity to speak of. Any string longer than 100 characters is trivially not a concatenation of two words.
planede 4y ago
Have a rolling hash and compute all hashes of the prefixes in one go, in O(N). Per-prefix cost of hashes gets amortized to O(1).

jameshart 4y ago

It’s O(n) in an n that doesn’t matter. The length of that word does not grow arbitrarily long, causing the asymptotic behavior of your algorithm to dominate. Because it’s a word. In the case of ‘is this word of length n the result of concatenation two English words’, the time complexity as n approaches infinity is constant, because once you get past floccinaucinihipilificationantidisestablishmentarianism, any longer word than that you can just return ‘false’ immediately.

krackers 4y ago
Right, for all practical purposes if the reader assumes the words are from the English language, you can assume that comparisons will be constant (both from the pedantic CS perspective since words are bounded in length, and also from a practical perspective since the bound is small, and with SIMD can be done fast enough for most words). See also responses from https://news.ycombinator.com/item?id=35550842 https://news.ycombinator.com/item?id=35550842 and https://news.ycombinator.com/item?id=35551114 https://news.ycombinator.com/item?id=35551114 which say the same better than I could. It feels really disingenuous when interview questions start off posing a seemingly innocent problem where the intuitive and practical answer is usually the one that'd you go for if you wanted to implement this in the real-world, then as soon as you answer the interviewer turns around and throws a hidden assumption at you. You could argue that the point of the interview is to have the candidate suss out these things, but it's usually a one-way discussion where you're not allowed to even question if the assumptions make sense in the real-world (which is what you ultimately care about). And if the words are truly big enough to be an issue then you better start being rigorous and benchmarking different approaches rather than just handwaving big-o. Ultimately when you get down to it, the whole point seems to see if the interviewee can be led down the pre-determined golden path, even if the path is only fools gold.
yongjik 4y ago
I see, yes I think you do raise a very good point, but on the other hand, the issue could be quickly resolved by talking about it. Any good interviewer would say something like "Ah yes that's a very good point, I forgot to consider the implication of the English vocabulary. However, for the sake of this interview, let's assume the 'vocabulary' is made of strings that can be arbitrarily long. Does that change your answer?" After all, if we assume that all words are at most, say, 50 characters long, then there's no asymptotic complexity to speak of. Any string longer than 100 characters is trivially not a concatenation of two words.

planede 4y ago

Have a rolling hash and compute all hashes of the prefixes in one go, in O(N). Per-prefix cost of hashes gets amortized to O(1).