Maybe they intentionally asked you an impossible question that is not obviously unsolveable to see how you react when given and how you approach hard problems.
1. You either know immediately that it is impossible and you say so, which means you've encountered the problem and its related research before.
2. You are a savant, like Kim Peek, and work out the solution to a PHd level research problem in your head in a few minutes, giving the answer that it is impossible.
3. Pretend to be (2) by already knowing (1), but having a good poker face and then faking an "Ah ha!" moment
4. Sit there, unsure, feeling stupid, wondering if you're supposed to know the answer to this already or if you're supposed to be smart enough to figure it out.
I'm having a lot of trouble figuring out how any of these outcomes are in any way beneficial to the interview process.
There are more option than the following scenarios:
(1-3). Know the solution already or be a genius and find the solution surprisingly fast.
4. Sit there feeling stupid.
The idea is to give you an extraordinarily hard problem without the expectation that you'll solve it. The reasoning of the employer is the following:
I. You fall into the options (1-3) and you are either a genius or the question was too easy. Either way its not bad for you.
II. You don't have enough knowledge at hand to approach the problem. Then you do either what described in option 4. xor you accept and be honest when you don't know something and you know what to do next; identify information you are missing and how you can get it.
Since the case I. is rare and the case II. gives the employer a good picture of you it's a good question for an interview.
I got decently far, I would say, all things considered. I was able to lay out the problem domain well - determine what the requirements were, all that - then start by breaking the problem down into bits.
I did hit walls, understandably, which ultimately ended the interview with a lot of "hmmm, not really sure. Maybe this? No? Oh... Hm... [..]"
