A cache that forgets the oldest
Reported in interviews at (where)
Build LRUCache, a store of whole-number keys and values that holds at most capacity keys.
LRUCache(capacity) starts empty.
get(key) returns the value stored for key, or -1 if the key is not in the cache.
put(key, value) stores value for key, replacing the value the key had. If that adds a new key to a full cache, the key that was used longest ago leaves first.
A get of a key that is in the cache and every put count as using that key. Aim for O(1) time per call.
- Input
["LRUCache","put","put","get","put","get","get","put","get"]
[[2],[1,10],[2,20],[1],[3,30],[2],[3],[1,15],[1]]- Output
[null,null,null,10,null,-1,30,null,15]
Reading key 1 makes key 2 the one used longest ago, so adding key 3 pushes key 2 out. Putting key 1 again only changes its value.
- Input
["LRUCache","put","put","get","put","get","get"]
[[1],[7,1],[7,2],[7],[8,3],[7],[8]]- Output
[null,null,null,2,null,-1,3]
With room for one key, key 8 replaces key 7.
Limits
1 <= capacity <= 30000 <= key <= 100000 <= value <= 100000at most 20000 calls after the constructor
Hints
Hint 1
A hash map finds a key in O(1); something else has to remember the order the keys were used in.
Hint 2
Keep the keys in a doubly linked list, most recently used at one end: a use moves a node to that end, and the other end is the key to evict.
Where this was reported
- Microsoft, SDE-1 on-campus interview (GeeksforGeeks)
- Flipkart, SDE-1 interview (GeeksforGeeks)
- Goldman Sachs, Analyst technology interview, 2026 (Reddit)
- Societe Generale, SDE on-campus interview, 2021 (GeeksforGeeks)
- Intuit, SWE intern campus interview, 2026 (LeetCode)
- Oracle, 6-month intern campus interview, 2025 (Medium)
- Flipkart, SDE-1 interview, 2025 (PrepInsta)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.





