Most common phone interview question at Google

Post by asdginioubnou » Sun, May 03, 2020, 12:50 AM UTC

v_g wrote: post #21

asdginioubnou wrote: post #13

Both solutions are O(1). The alphabet is finite. Let's say there are M different characters in the alphabet and N different characters in the string. If there is a duplicate, it is guaranteed to occur within the first M + 1 characters of the string by the pigeonhole principle. As N grows without bound, the number of characters that needs to be checked reaches a limit. (I guess, most precisely, we should define K to b…

Interesting point. However, Alphabet is probably not the best example, Unicode perhaps? The upper bound in Unicode is ~ 1.1 Million, but still fixed

Post by aeyes » Sun, May 03, 2020, 2:31 AM UTC

ayberk wrote: post #4

I used to use this question before it became too common. Any reasonably-well-prepared candidate should be able come up with the O(N) solution and the follow-up is always good for a discussion: "what if the string is huge but the alphabet is small? Eg, a DNA sequence." There's a single pass solution that's left as an exercise for the reader.