I interviewed for a QA position at (Deleted to protect the guilty) where I had to answer a bunch of brain teasers like this. I always prepare thoroughly and even enjoy solving these sorts of puzzles, so I knew most of the standard ones by heart and did fine. I would say that about half of the people who interviewed me did not appear to have the mental acuity to answer such questions themselves. I did learn some new and interesting puzzles though!

Two months later I was hired for what turned out to be an excellent software development position at a completely different organization.

When I interview technical candidates, I ask a pair of related questions that encompass data structures, sorting, and time complexity. It is a very simple-sounding problem. The good candidates get the questions almost before I finish asking, and the mediocre candidates struggle.