Design and implement an LRU cache with O(1) get and put
Reported in X (Twitter) USA engineering loops. Hash map plus doubly linked list problem bridging DSA and system components.
Interview scenario
Context for X (Twitter) candidates:
Capacity is fixed; evict least recently used entry when inserting beyond capacity.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at X (Twitter): Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Combine a hash map (key → node) with a doubly linked list ordered by recency. Head = most recent, tail = LRU. On get: move node to head. On put: update or insert at head; evict tail if over capacity.
Operations: splice node out of list and add to head in O(1); map gives O(1) lookup. Total get/put amortized O(1).
In Java, LinkedHashMap with access-order and overridden removeEldestEntry is acceptable if you explain internals. In interviews, coding the list + map shows deeper understanding.
System design tie-in: LRU is a common eviction policy in CDN, database buffer pools, and CPU caches—discuss trade-offs vs LFU and TTL-based expiry.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.