I have to admit here, that I am one of those who like to ask algorithm questions in interviews, but I have to stress, that the actual answer to the question is absolutely irrelevant. I do not care the slightest if the interviewee knows the answer or not. Instead, for me, this question targets different aspects, like the following - in order of importance:
Such questions are deliberately under-specified. In your example, there are no further details given about the sequence. If you have an interviewee who asks you whether these numbers are actually sorted, then that's a good sign. He has the correct mindset to ask customers on further details, that will help coming to a better solution in a shorter time. The candidate may also toy with the idea of using O(n) space to store an array of N numbers, but he should not do that without asking about more details on X and Y. Let's say that X and Y are between 1 and 1000, then sure, go ahead and fire up an array-based solution. But if I tell you the interval is 1 and 1 billion, then the problem becomes a totally different one. Let me stress again, that I don't care about the solution. I want to see if the candidate can find the distinction between these problems, which are immensely different.
I do not want to hire a programmer who doesn't even know what O(n) means. That's an absolute must-know if you had any decent education in that area. But it's also important to not just know what it means, but to actually apply that knowledge. In your example, I want a candidate to realize that he is not allowed to sort the data (without asking further questions targeting the option of a bucket sort or other O(n) sort approaches) due to sorting required O(n log n) in general.
Similarly, other algorithm questions target standard techniques like tree- or graph-traversal, or recursion. A candidate may slip at one of these techniques, which does not make a good impression. In such cases, however, I like to dig deeper to find out whether the candidate has any CS background at all. Of course, it depends on what the target position is, but usually a developer who doesn't know about runtime complexities, nor typical data structures and their traversals, is not going to be any help.
After asking the question, you monitor the candidate closely. How does s/he react? You get the best results here from candidates who have absolutely no clue on how to solve the problem at first. In that respect, the question checks what might happen if a similar situation occurs at the workplace later. You may happen across such a problem during your development, and it is good to know how your candidate deals with these problems, even if s/he is not able to solve it all by themselves.
Example: You do not want your candidate to go into silent mode for the next half hour! Check if he can come up with intelligent questions (see Requirements), check if he starts thinking out of the box once he realizes he cannot do it. Even a "fun" counter-question like a "May I use the phone-a-co-worker option?" is a good sign.
How to answer
In general, the best answers you can give for these kind of questions are counter-questions! Telling an answer right-away basically fails the whole thing, and is in fact not a good answer at all, because all of these question hint at trade-offs, which your answer implies, without you having the required information yet to intelligently make that trade-off. Of course, the quality of the counter-questions varies between candidates.
As a general note on interview questions: Counter-questions are seldomly a bad thing. In one of my own interviews I was for example asked something like the following: "If you would have to implement X, would you choose C++ or Java for that, and why?" - I simply countered with "Am I limited to these two?". Guess for yourself, what kind of reaction you get from an interviewer for such a counter-question - and how easy it makes it for you to actually show the interviewer what you're capable of.