Design and implement an LRU cache with O(1) get and put
Reported in Ubisoft European engineering loops. Hash map plus doubly linked list problem bridging DSA and system components.
Interview scenario
Context for Ubisoft 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 Ubisoft: 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.