I should have been clearer. After thinking for a bit I did start asking questions, but the interviewer didn't give me any useful information. IIRC I asked if I could assume the problem was small enough that I could just do a brute force search of possible solutions and the answer came back that no, they needed a solution which would work for any size; I know I asked other questions but I can't remember what they were.
I wasn't silent for half an hour, just for the first couple minutes; but I didn't write any code (which is what the interviewer was pressing me to do).
(Speaking of entirely new algorithms though, there was an interview question which was a thinly disguised 3SUM, and they expected the very obvious N^2 solution; my interviewers were shocked when I pointed out that the way they had structured the problem, the density was high enough to use a convolution and solve it in N log N time.)
What structure should there be for nlogn solution to be applicable?
The issue isn't structure but rather density. If you have N values ranging from -M to M, the "obvious" solution is O(N^2) and the convolution us O(M log M). So if you have lots of values within a narrow range the convolution wins.
If I may ask, why in that interview did you just sit there and not ask any questions? I've passed code interviews where I learned an entire new algorithm on the fly (funny how knowing there is an nlogn solution to an n**2 problem can produce workable solutions).