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.)