I'm not at all a fan of gotcha puzzles, but I tend to think this is not one, at least not purely. It allows you to judge quite a broad range of problem solving approaches. You can argue about this puzzle not being relevant to a developer's day job and there's certainly merit to that, however I would argue that the part about realizing that the badly performing brute force approach is allowed is very relevant. The performance analysis and optimization maybe not in so much detail, though having a rough grasp of it been also be useful when there are concrete performance issues (but let's be honest: you can spend a lot of time without running into them).

I found one sentence very interesting:

> Moreover, the problem as I present it, has enough range to sift out bad candidates from good ones even if the candidates have seen the problem before, which is why I successfully used it even though it was banned at Google.

How do you measure the question's success? Is there some kind of feedback you get about how the person you made a decision about went on to perform? What about the people that ended up not being hired?