[chrisseaton]

> Any reasonably-well-prepared candidate

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?

[ayberk]

> 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.

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.

[chrisseaton]

> It's actually two passes: one to create the set, and one more again to find the character.

Those are combined into a single pass in the example in the article, aren't they?

[bootloop]

Yea I don't understand what the parent comment wants to say. You need to have a lookup structure (even if its only a bit) and then you can do one pass over the string. The lookup or adding a character doesn't count as a pass. And there is no way to omit this anyway.

[bootloop]

Well you can also use a single byte bitmap and check if a bit for a character was already set. That gets real fast real quick.