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.
True puzzles do not provide very much useful information, as they are often based on a trick, and don't actually overlap a lot with what we do. Even algorithmic puzzles are pretty dumb.
But problem solving, O(n), and composing algorithms is very important to what we do. So what I'm looking for when I ask you to write a function so solve X is:
- Can you understand a problem and critically think about it?
- Can you handle super-basic logic to work out a solution?
- Do you at least vaguely understand performance concerns, i.e. can you identify whether a given input is problematic, or talk about possible ways to improve it?