I see what you are saying. I was initially thinking about using dynamic programming, and surely I could illustrate my chops (or not) in that regard. But what if I do have that 'aha' moment, or I just remember that trick? Now you are not measuring my ability to think about these things on my feet, but either get no info (if I just regurgitate the answer), or get to evaluate my acting skills if I decide to pretend to 'figure it out'. And still, none of those, whichever way it goes, really answer how I do in production. I have come across plenty of really 'puzzle' clever people that cannot really pull together working code for a complex problem, and those (like me) who are just terrible at them, but really deliver (ignore that I'm patting myself on the back here, that's not the point, it's just a data point I know well). For example, I am terrible at chess. I'll move a piece into a lane where they can be attacked with impunity. The same goes with computers. Plenty of times I'll miss something obvious, for a short time (like the length of an interview). But I compensate for that with things like unit tests, thinking in the shower and then coding at work, and so on. Take it on faith that it works and I produce.
For example, let's say I need to hire somebody to do a lot of low level optimizations. I can ask them some specific problem, and keep saying 'make it faster'. Or, I could start talking to them about cache misses, and see if we can just talk about it. Anyone that can actually do the work will be bringing up the pipelines, out of order instruction executions, the costs of going off chip, how to organize data and programs to minimize cache misses, well, the whole ball of wax. In that context I can start feeling out if they are original thinkers, or just plodding followers of some rules they read on HN or somewhere. If they don't have experience in this, but I think they might be good at it, I can talk about their debugging skills, or some other engineering/optimization problem that they have solved. I'll admit that this all presupposes an existing career - I do find it harder to interview and evaluate recent grads because it is all speculation at that point. Heck, if all you have done is CRUD apps I can see if you have thought about the good/clean code vs put it together to get it out the door to get market share issues. There is no one, clear, obvious answer, and a good mind will see that, and be able to free associate about it. A mediocre mind will repeat whatever HN quote resonated with them when they read it. If you can think about that clearly, you can learn the micro-architecture and then use the same style of thinking to optimize code.
So, all of that is why I don't like 'aha' questions, or even reverse the string questions. I don't think it has any predictive value. Certainly, Google, which asks tough algorithmic questions, admits that with all their collected data they see no correlation between interviews and performance, except for the situational type interview stuff I write about (and that the OP wrote about).
Asking this question in a real interview, if the candidate missed the summation approach and used an array to keep counts, I'd simply say "That sounds good. What if we were really worried about memory use? Could we do it with less memory?"
This is what it's supposed to feel like when Interview Cake offers the "gotcha" that we can solve the problem with O(1) additional memory after you say you have an answer, before showing you the final solution. In real life I wouldn't fault the candidate for needing the nudge.
Another flow I've considered is to make the question multi-part, with the second part (the "follow-up" question) adding the O(1) time constraint. I'm worried that with this flow, in the case where you do jump right to the summation approach, the app will feel naive because it will pose a whole new question that you've already answered.
So far I think the best approach is to keep the current flow but use a less harsh word than "gotcha." What do you think? Do you still think the question is just fundamentally too much of an "aha"?
(I agree that if the candidate jumped right to the summation answer on this one it's a weak signal. I wouldn't ask this question in an interview--it's not my favorite either, and it's unfortunate that it's a common one. My favorites aren't on the site yet because they're hard to explain without pictures. Adding those pictures is the next project!)
Nitpicking because this tripped me up: You can do this in-place and in O(n) time by repeatedly partitioning the array in half (by value) and discarding the smaller half. I'd have needed a hint that you can do it in one pass to have noticed the summation approach.
For example, let's say I need to hire somebody to do a lot of low level optimizations. I can ask them some specific problem, and keep saying 'make it faster'. Or, I could start talking to them about cache misses, and see if we can just talk about it. Anyone that can actually do the work will be bringing up the pipelines, out of order instruction executions, the costs of going off chip, how to organize data and programs to minimize cache misses, well, the whole ball of wax. In that context I can start feeling out if they are original thinkers, or just plodding followers of some rules they read on HN or somewhere. If they don't have experience in this, but I think they might be good at it, I can talk about their debugging skills, or some other engineering/optimization problem that they have solved. I'll admit that this all presupposes an existing career - I do find it harder to interview and evaluate recent grads because it is all speculation at that point. Heck, if all you have done is CRUD apps I can see if you have thought about the good/clean code vs put it together to get it out the door to get market share issues. There is no one, clear, obvious answer, and a good mind will see that, and be able to free associate about it. A mediocre mind will repeat whatever HN quote resonated with them when they read it. If you can think about that clearly, you can learn the micro-architecture and then use the same style of thinking to optimize code.
So, all of that is why I don't like 'aha' questions, or even reverse the string questions. I don't think it has any predictive value. Certainly, Google, which asks tough algorithmic questions, admits that with all their collected data they see no correlation between interviews and performance, except for the situational type interview stuff I write about (and that the OP wrote about).