[acchow]

This question involves an "a-ha" moment (for the linear-time solution) and was thus banned from interviews at Google last year.

Don't use questions involving eureka moments. They reveal nothing about the candidate.

Edit: It should be noted that this question was used for a long time at Google, Microsoft, and many other places. It's a terrible question.

[huhtenberg]

No, it doesn't involve the "a-ha" moment.

Two-pass solution is obvious, just look at the final state. Once you are at that, the one-pass is a run-of-the-mill optimization of switching from accumulating and then processing the state to doing it all in parallel. The ability to recognize when this is doable is a good way to tell someone who's done it before (in some other context) from those who merely wrote a functional prototype of Tic-Tac-Toe in TurboPascal.

[InclinedPlane]

I find it's best to ask easy questions (like fizzbuzz) and very hard questions. For easy questions you gauge fundamental competence, those should be things that decent devs can solve as fast as they can write, it makes it easy to weed out the folks who are clueless and somehow have trumped up resumes. For hard questions you go in with the expectation that you're not going to get a solution to the problem, so you concentrate on observing the process the candidate uses, their problem solving skills, communication, the sort of problems they're comfortable with tackling, and so on.

[nick_ok]

the word you are looking for is insight problem. Insight problems are problems in which people unable accurately predict their progress. As in if you asked someone to continually report their progress on a problem as they attempted to solve it they would say something like, "0% 0% 0% oh I'finished". Insight problem solving is a topic of significant interest in cognitive science right now and most recently it was found that applying a small amount of electric current to the right side of the brain greatly increase our capacity for insight problem solving. It is pretty dope.

[Camillo]

How much current? Do you think it would be doable to make a "thinking hat" to wear at job interviews?

[nick_ok]

This all came to light in 2011 so pretty recent. Also not only may it be possible, but the term 'thinking cap' has already been used to refer this very invention, namely transcranial direct current stimulation (tDCS). If you are interested check out this article, http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjourna... However I would not get your hopes to high up. It is unlikely that prolonged exposure would be particularly healthy and i imagine you would get diminishing returns.

[asveikau]

Is there a definition of ah-ha moment? Seems like what strikes one person as an "ah-ha" insight might be a baseline assumption of another person's thought process.

[raverbashing]

It means (I think) that the trough between the "good answer" and the "bad answer" is too big. So basically either you know it or not and can't "grow" toward a solution easily

I hate this kind of problems.

[etler]

I think it can be summed up to; you're expecting a specific final solution. Open ended questions that don't have a best solution will require you to pay more attention to the process, rather than the result. In this article, the guy was smart enough to figure it out, but during the pressure of the interview, didn't stumble upon the right solution or fully verify his initial solution, but was able to as soon as the pressure was off. With an open ended solution it's not about getting it right, but how you try to come up with an answer.

[daGrevis]

I think this explains it.

http://en.wikipedia.org/wiki/Eureka_effect

[acchow]

> Is there a definition of ah-ha moment?

Not an exact definition, no. But if a question is exceedingly simple after one tiny bit of insight that doesn't require much analytical thinking to arrive at, that certainly falls into the category.