[huhtenberg]

> The next day I showed this question to my TA, who's a PhD student in theoretical computer science. After 40 minutes he was also stuck with nothing.

That just doesn't speak well of this particular PhD. The one-pass solution is rather obvious. I hate puzzle-based interviews with passion, but this is actually a very reasonable question and it does help to tell apart people with "theoretical" computer science skills from those with a bit more practical experience.

[msohcw]

Definitely agree. As a problem, this is pretty easy. Ask anyone that does competitive algorithmic programming. The linear solution is obvious, I wouldn't say that it requires a eureka moment, even though I didn't bother thinking of the one pass because the difference would be minimal at best (for most inputs.) OP should share what his internship was about, I'd disagree if it had more to do with understanding practical implementation and development than efficency and algorithms. Both are valid skillsets equally useful to twitter.

EDIT:apologies to whoever had to kill the extra posts, my mobile hn client is on the fritz.

[etler]

Not all theoretical CS is focused on algorithms, and if this were specifically for an algorithm focused position, I would ask a more in depth and relevant question. This question might be suited for a small subset of jobs, but considering that the guy is still in school doing internships, I would assume the position was a generic software developer position, which makes this a bad question.

[JanezStupar]

While I do not think that the problem is hard in a sense that if you came to me and wanted it solved for you I couldn't do it. I do think that it is a horrible interview question.

I fail to see why one would ask this kind of question and what one would take away from the answer.

How does being able to solve problem like this help make Jack Dorsey richer and more respected? How does it help Twitter users have a better experience? How does it help the interviewer assess whether this dude on the other side will make his life more bearable by not shitting all over the carpet?

I think it is mostly a form of geek bullying and intellectual mastrubation for its own sake. I have a message for the people running companies where these kinds of hiring practices are taking place. You have some insane geeks on the loose and you should catch them and lock them into the darkest dungeon as they __will__ ruin your company.

[huhtenberg]

It's a test question, duh. You struggle with it - you clearly lack field experience. It doesn't make you an idiot, it doesn't disqualify you as a programmer, it merely tests whether you have a particular basic skill or not.