I dealt with this recently. Was asked to implement a LRU cache. I knew the trick, use two data structures to keep things sorted and accessible in constant time.

I dealt with this recently. Was asked to implement a LRU cache. I knew the trick, use two data structures to keep things sorted and accessible in constant time. Could do it in my sleep. Had to pretend I had never seen it before, started with a non optimize d solution and added the correct pieces to make it optimal. Interviewer seemed miffed, kept adding tests to see if my algorithm would get the wrong answer and seemed upset that I got it right. It was bizarre. Didn't get the job, didn't remember the answers to a few of the other questions, though I found them post interview.