If I had asked a question like that, and if you can do some bitwise voodoo to solve it in O(n), great. But what I'd be looking for is, can you solve it all? Do you understand the problem statement enough to write a general sort of algorithm? If your first pass is O(n^4) and I point it out, can you understand this, and think of ways to improve? If I point out a problematic or erroneous input, can you reason about what will happen? Etc.
I think this is what we need to look for in interviews. Certainly not, can you solve this brain teaser I read in a magazine.
I've definitely encountered questions where I wasn't familiar with a certain topic, and usually they'll realize it and just give me hints. I did also have interviewers who just watched me struggle though.