I suggested a solution for LRU Cache using LinkedHashMap but the interviewer said it was "too trivial" and wanted me to do another way using a combination of HashMap with values as nodes. It was all very strange. I suggested using ArrayList but the interviewer said it was O(n) lookup like LinkedList so it wouldn't work. I think the interviewer was terribly wrong.