Hacker News Reader

Comment by ayberk | Hacker News Reader

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.

View on HN

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

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.

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

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

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.

Going to ask the obvious question: Did 70% really want to solve this with a double for loop?

I don't see what changes with a small alphabet. Or are you searching for multiple ocurrences of sequences instead of single characters?

i will still have to iterate through the string and the hash/dict for a small alphabet is not taking up a lot of space. by the wording it sounds like maybe you want people to use bitflags but your problem still seems solvable with the blog's solution (hash/dicts)

Reply on news.ycombinator.com