DSA interview question

LRU Cache

Medium · Data structures · Topics: hash map, doubly linkedlist, design

The problem

An image CDN keeps the most recently used thumbnails in memory, up to a fixed capacity. get(key) returns a cached value (or −1) and marks it as recently used. put(key, value) inserts or updates an entry, and when the cache is full it evicts the least recently used entry. Both must be O(1). A hash map gives O(1) lookup, and a doubly linked list ordered by recency gives O(1) "move to front" and "remove from back". The map stores list iterators, so the two stay in sync.

Example: capacity 2: put(1,1), put(2,2), get(1) → 1, put(3,3) evicts key 2, so get(2) → -1.

Function signature

class LRUCache {
public:
    explicit LRUCache(int capacity);
    int get(int key);               // -1 if absent
    void put(int key, int value);
};

Test cases

Operations (capacity)	Output	Explanation
(2) `put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4)`	`1 -1 -1 3 4`	LeetCode's example
(1) `put(1,1) put(2,2) get(1) get(2)`	`-1 2`
(2) `put(1,1) put(2,2) put(1,10) put(3,3) get(2) get(1)`	`-1 10`	Updating 1 refreshed it, so 2 was evicted
(2) `put(1,1) put(2,2) get(1) put(3,3) get(2) get(3)`	`1 -1 3`	get also refreshes

(Confirm: both get and put count as "use"; capacity ≥ 1; O(1) average per operation.)

How interviewers phrase it

"Design a data structure that follows the Least Recently Used cache constraints, with get and put in O(1) average time" (LeetCode 146).

Clarifying questions to ask

Does get count as a use? (Yes.)
Does updating an existing key count as a use? (Yes.)
May I use library containers such as std::list? (Usually yes; some interviewers want a hand-written list.)

Follow-ups to expect

"Why a doubly linked list?"
"What does the hash map store?"
"How do you move an entry to the front in O(1)?"
"What happens on eviction?"
"Thread safety or TTL?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview