Design a Least Recently Used (LRU) cache that supports get and put operations, both in O(1) time.
The cache has a fixed capacity. When adding a new item exceeds the capacity, the least recently used item should be evicted.
For example, with capacity 2:
put(1, "A") -> cache: {1: "A"}
put(2, "B") -> cache: {1: "A", 2: "B"}
get(1) -> returns "A", now 1 is most recently used
put(3, "C") -> evicts key 2 (least recently used), cache: {1: "A", 3: "C"}What data structures would you combine to achieve O(1) for both operations? How do you track usage order efficiently?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
A hash map gives O(1) lookup, but how do you track the order of usage?
- Hint 2
A doubly linked list allows O(1) insertion and removal if you have a direct reference to the node.
- Hint 3
Combine a hash map (key to node reference) with a doubly linked list (ordered by recency). The most recent item goes to the head, and eviction removes from the tail.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.