AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content

02 LRU cache / Lesson 1 of 1

LRU cache

12 min · +10 XP · 2 exercises · 4 questions

Read the text12 min
Exercises0/2
Quiz4 q

Quick answer

How do you implement an LRU cache in Java?

Keep a HashMap from key to node and a doubly linked list of those nodes in order of use, with head and tail sentinels. get finds the node through the map and moves it after the head; put adds a new node there and, when the cache is full, removes the node before the tail and its map entry. Both run in O(1).

The most asked machine-coding problem, because one line of the brief decides the design: get and put in O(1). The full treatment, with the code in four languages, is the note Design an LRU Cache; this lesson is what you need to code it in twenty minutes.

Two structures, one object

  • A HashMap<String, Node> finds any entry in O(1) but keeps no order.
  • A doubly linked list keeps the order of use: most recent after head, least recent before tail. Unlinking a node you already hold is O(1) because it knows its prev.
  • The map's values are the list's nodes, so a lookup lands on the node to move.
  • head and tail are sentinels: never removed, so insert and unlink need no null checks.
An LRU cache is a map of nodes plus a doubly linked list

One class faces the caller: get and put, a fixed capacity, a HashMap from key to node, and the two sentinel nodes that bound the list.

0:01 / 0:09Step 1 of 3
Transcript · 3 steps

Watch the order move

Capacity 3. A hit moves its node to the front; a put on a full cache evicts from the back.

LRU cache, capacity 3: hits move to the front, the tail is evicted
PUT 1 A, PUT 2 B, PUT 3 C, GET 1, GET 2, PUT 4 D, GET 3, PUT 5 E

PUT 1 into an empty cache: a node goes after head and into the map. head and tail are sentinels, never removed, so no null checks.

0:01 / 0:24Step 1 of 8
Transcript · 8 steps
  • get = map lookup + unlink + addFirst.
  • put of a new key into a full cache: unlink tail.prev, delete its key from the map, then add the new node. Evict first, so the size never passes capacity.
  • put of an existing key updates the value and counts as a use.
  • A miss changes nothing.

Time without a clock

The second program adds expiry. Never call System.currentTimeMillis() in a design you must test: keep a logical now that a TICK command advances, store expiresAt on each node, and treat an entry as gone once now >= expiresAt.

  • A GET of an expired entry removes it and says so.
  • A PUT into a full cache drops expired entries before evicting a live one: an expired entry is worth nothing.

The traps

  • A singly linked list: unlinking needs the predecessor, so every get walks the list.
  • Forgetting the key in the node: eviction cannot find the map entry to delete.
  • Printing from a HashMap: list the order by walking the linked list from head.

Common questions

Can I use LinkedHashMap for an LRU cache in Java?

Yes: new LinkedHashMap<>(16, 0.75f, true) keeps entries in access order, and overriding removeEldestEntry to return size() > capacity evicts the least recent one. In a machine-coding round, mention it and then build the map and list yourself, because that is what is being tested.

Does a get on a missing key change the LRU order?

No. A miss touches no node, so the order of use is unchanged. Only a hit, or a put of a key, makes that key the most recent; a read that must not count, such as a peek or a debug listing, should walk the list without moving anything.

How do you add TTL expiry to an LRU cache?

Store an expiry time on each node and read time from a clock you pass in, not the system clock, so tests are repeatable. A read of an expired entry removes it and reports a miss, and a put into a full cache drops expired entries before it evicts a live one.

Why does each node store its key?

Eviction starts from the list: the node before the tail is removed, and the cache must then delete its map entry. The node is all it holds at that moment, so the node must carry the key.

Mark as readSign in to keep your place.
AI InterviewGet started

LRU Cache in Java: HashMap Plus Doubly Linked List Design

Code an LRU cache in Java with O(1) get and put: a HashMap of nodes, a doubly linked list with sentinels, tail eviction and TTL on a logical clock.

How do you implement an LRU cache in Java?

Keep a HashMap from key to node and a doubly linked list of those nodes in order of use, with head and tail sentinels. get finds the node through the map and moves it after the head; put adds a new node there and, when the cache is full, removes the node before the tail and its map entry. Both run in O(1).

Lesson

The most asked machine-coding problem, because one line of the brief decides the design: get and put in O(1). The full treatment, with the code in four languages, is the note Design an LRU Cache; this lesson is what you need to code it in twenty minutes.

Two structures, one object

  • A HashMap<String, Node> finds any entry in O(1) but keeps no order.
  • A doubly linked list keeps the order of use: most recent after head, least recent before tail. Unlinking a node you already hold is O(1) because it knows its prev.
  • The map's values are the list's nodes, so a lookup lands on the node to move.
  • head and tail are sentinels: never removed, so insert and unlink need no null checks.
LRUCache- capacity: int- map: Map<String, Node>- head, tail: Node+ get(key): String+ put(key, value): String- unlink(n)- addFirst(n)Node+ key: String+ value: String+ prev: Node+ next: Nodemap valueshead, tail2
An LRU cache is a map of nodes plus a doubly linked list.
  1. One class faces the caller: get and put, a fixed capacity, a HashMap from key to node, and the two sentinel nodes that bound the list.
  2. The map's values are the list's own Node objects. A lookup lands on the node, and head.next is always the most recent entry, tail.prev the least.
  3. Each Node points both ways. unlink rewires its two neighbours and addFirst puts it after head — six pointer writes, whatever the cache's size.

Watch the order move

Capacity 3. A hit moves its node to the front; a put on a full cache evicts from the back.

head5:E4:D2:Btail1:Aevictedmost recentleast recentmap: {2, 4, 5} size 3/3PUT 5 E→ stored 5, evicted 1
LRU cache, capacity 3: hits move to the front, the tail is evicted. Example: PUT 1 A, PUT 2 B, PUT 3 C, GET 1, GET 2, PUT 4 D, GET 3, PUT 5 E
  1. PUT 1 into an empty cache: a node goes after head and into the map. head and tail are sentinels, never removed, so no null checks.
  2. PUT 2 goes in after head too, pushing 1 one place towards the tail. Newest first, oldest last: the list is the order of use.
  3. PUT 3 adds a new node after head, so the newest key is always the most recent. The cache holds 3 of 3.
  4. GET 1 is a hit. The map hands over node 1, which unlinks itself from position 3 and goes after head: the order is now 1, 3, 2.
  5. GET 2 is a hit. The map hands over node 2, which unlinks itself from position 3 and goes after head: the order is now 2, 1, 3.
  6. PUT 4 finds the cache full, so the node before tail goes first: key 3, the least recently used, leaves the list and the map. Then 4 goes in after head.
  7. GET 3 misses: key 3 was evicted earlier. No node is touched, so the order stays 4, 2, 1.
  8. PUT 5 finds the cache full, so the node before tail goes first: key 1, the least recently used, leaves the list and the map. Then 5 goes in after head.
  • get = map lookup + unlink + addFirst.
  • put of a new key into a full cache: unlink tail.prev, delete its key from the map, then add the new node. Evict first, so the size never passes capacity.
  • put of an existing key updates the value and counts as a use.
  • A miss changes nothing.

Time without a clock

The second program adds expiry. Never call System.currentTimeMillis() in a design you must test: keep a logical now that a TICK command advances, store expiresAt on each node, and treat an entry as gone once now >= expiresAt.

  • A GET of an expired entry removes it and says so.
  • A PUT into a full cache drops expired entries before evicting a live one: an expired entry is worth nothing.

The traps

  • A singly linked list: unlinking needs the predecessor, so every get walks the list.
  • Forgetting the key in the node: eviction cannot find the map entry to delete.
  • Printing from a HashMap: list the order by walking the linked list from head.

Common questions

Can I use LinkedHashMap for an LRU cache in Java?

Yes: new LinkedHashMap<>(16, 0.75f, true) keeps entries in access order, and overriding removeEldestEntry to return size() > capacity evicts the least recent one. In a machine-coding round, mention it and then build the map and list yourself, because that is what is being tested.

Does a get on a missing key change the LRU order?

No. A miss touches no node, so the order of use is unchanged. Only a hit, or a put of a key, makes that key the most recent; a read that must not count, such as a peek or a debug listing, should walk the list without moving anything.

How do you add TTL expiry to an LRU cache?

Store an expiry time on each node and read time from a clock you pass in, not the system clock, so tests are repeatable. A read of an expired entry removes it and reports a miss, and a put into a full cache drops expired entries before it evicts a live one.

Why does each node store its key?

Eviction starts from the list: the node before the tail is removed, and the cache must then delete its map entry. The node is all it holds at that moment, so the node must carry the key.

Exercises

LRU cache

Write an LRUCache with O(1) get and put using a HashMap from key to node and a doubly linked list with head and tail sentinels. The first line of input is the capacity (at least 1); then commands, one per line. Keys and values are single words.

CommandPrints
PUT <key> <value>stored <key>, or stored <key>, evicted <old> when a new key fills a full cache, or updated <key> for a key already there
GET <key>the value, or miss
ORDERorder: <keys from most to least recently used>, or order: empty
anything elseerror: unknown command <WORD>

A GET hit and any PUT make the key the most recently used; a miss and ORDER change nothing. A full cache evicts the least recently used key.

LRU cache with expiry

Extend the cache with time-to-live on a logical clock: time starts at 0 and moves only on TICK. An entry put at time t with ttl n expires at t + n, and is expired once now >= t + n. The first line is the capacity; then commands:

CommandPrints
PUT <key> <value> <ttl>updated <key> for a live key already there (new value, new expiry, most recent); otherwise stored <key> or stored <key>, evicted <old>
GET <key>the value (a hit moves it to the front); expired when the key is there but expired — it is removed; miss when it is not there
TICK <n>time <now> after advancing the clock by n
SIZEthe number of live entries (expired ones are dropped first)
anything elseerror: unknown command <WORD>

An expired key that is PUT again counts as new. When a new key meets a full cache, first drop every expired entry silently; only if the cache is still full, evict the least recently used live key.

In this module: LRU cache

← Checkpoint — From requirements to classes · Checkpoint — LRU cache →