Not for Apple or Google, but I've literally been asked impossible questions during some interviews at other big-names.
Maybe I should have recognized they were impossible and addressed the interviewer. They were usually very number-theory heavy problems. After a bit of research, I determined that it wasn't really answerable, and people have done PHD work at MIT, CMU, etc.. to investigate the question I was given 30 minutes to work on.
I don't lie about my qualifications. I'm not a PHD student, there is nothing on my resume or CV that would imply I'd be aware of some obscure (not something I'd consider important to comp sci like crypto) area of research... but still, asked these really oddball questions.
One of my Google interviewers asked me to implement the AdWords analysis backend from scratch: an online, high volume (high enough to need to partition the data across some kind of distributed storage) streaming dataset with a query load that the interviewer refused to define, even when pushed.
I was a bit non-plussed at that one. Still don’t know what he was really trying to get at.
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... [..]"
Maybe I should have recognized they were impossible and addressed the interviewer. They were usually very number-theory heavy problems. After a bit of research, I determined that it wasn't really answerable, and people have done PHD work at MIT, CMU, etc.. to investigate the question I was given 30 minutes to work on.
I don't lie about my qualifications. I'm not a PHD student, there is nothing on my resume or CV that would imply I'd be aware of some obscure (not something I'd consider important to comp sci like crypto) area of research... but still, asked these really oddball questions.