(I guess, most precisely, we should define K to be min(M + 1, N). Then the first solution is O(K^2) and the second solution is O(K))
EDIT: I assumed the first solution would compare each character to the characters visited so far, i.e.
for i in [0..N]
for j in [0..i]
if arr[i] == arr[j] return arr[i]
for i in [0..N]
for j in [0..N]
if arr[i] == arr[j] && i != j
return arr[i]
I mean "N characters in the string", i.e. the string is length N. There won't be N different characters.
Is this right? It's a quadratic not an order of magnitude difference isn't it? And can you be an order of magnitude faster in an O notation expression anyway? Isn't an order of magnitude a coefficient? Don't we drop coefficients in O notation?
I always use the precise meaning. It might be better for me to say "factor of ten" rather than "order of magnitude" if other people don't always use the precise meaning.
In the example case where s[0] == s[1], it might be an order of magnitude slower, if there's much object initialization for the lookup table.
It's not right, indeed
There's a single pass solution that's left as an exercise for the reader.
Isn't that the point? You say it like it's a problem, but it screens for someone who's reasonably prepared, which is probably what Google wants to do because they really start looking for the super-world-tier people they employ, because I guess that takes more time and resources.
> There's a single pass solution that's left as an exercise for the reader.
Doesn't the blog post already include a single-pass solution that works on a small alphabet?
Definitely. That's why it makes a good question for the initial screening. If you can't come up with the O(N) solution, there's very little chance you'll pass the on-site interviews.
> Doesn't the blog post already include a single-pass solution that works on a small alphabet?
It's actually two passes: one to create the set, and one more again to find the character. There's a solution you can do in only one pass through the string and one through the alphabet. Complexity is the same, but it's far fewer operations for the specific example given.
I don't see what changes with a small alphabet. Or are you searching for multiple ocurrences of sequences instead of single characters?
Really? I've a hard time believing this
Naive Big O is just as likely to be wrong as naive anything else.
I hope this isn't a genuine phone screen question, because if someone punted this at me as a pass/fail I'd fail them for being confused about how real computers and real languages work behind those nice clean-looking "if thing is in other_thing..." statements.
When searching through a sorted list, your first instinct should be to use binary search. Your first instinct should not be "well maybe the list is always small, so linear search would be faster." Write the safe, predictable thing and save the optimizations for later.