LRU Cache with TTL
LeetCode 146 grows up: entries also expire, and expired ones must never take space.
the brief
What you are building
A login service keeps user sessions in memory, so it does not hit the database on every request.
Memory is limited, so the cache holds at most capacity entries. When it is full, the session used longest ago goes first — least recently used (LRU).
Sessions also expire: each one has a time-to-live (TTL). An expired session must never be returned, and must never push out a live one.
must have
Requirements
put(key, value, ttlMs, now)stores the entry; it expires atnow + ttlMs. An entry is alive whilenow < expiry.- Every
putfirst throws away all expired entries. puton a key that is still in the cache replaces its value and its expiry, and makes it the most recently used.putof a new key into a full cache (after the clean-up) evicts the least recently used live entry.get(key, now)returns the value of a live key and makes it the most recently used. A missing or expired key returns-1(an expired one is removed).size(now)returns how many entries are alive atnow.
the contract
The Java API: class LruCache
Time is a parameter, not System.currentTimeMillis(), so every test is exact. Values are int; -1 means "not found".
public LruCache(int capacity)- At most
capacitylive entries. public void put(String key, int value, long ttlMs, long now)- Insert or update; may evict.
public int get(String key, long now)- The value, or
-1. public int size(long now)- The number of live entries.
- 1 ≤ capacity ≤ 10,000
- 1 ≤ ttlMs ≤ 10⁹
valuecan be anyint, negatives included (a stored-1simply reads back as-1)nownever goes backwards- up to 20,000 calls; aim for O(log n) or better per call
example session
Calls in, answers out
A cache of 2 sessions.
| call | returns | why |
|---|---|---|
new LruCache(2) | — | |
put("session:rahul", 1, 1000, 0) | — | expires at 1000 |
put("session:priya", 2, 5000, 0) | — | expires at 5000 |
get("session:rahul", 500) | 1 | rahul is now the most recently used |
put("session:amit", 3, 5000, 600) | — | full: priya is the least recently used, so she goes |
get("session:priya", 700) | -1 | |
get("session:rahul", 1000) | -1 | 1000 < 1000 is false: expired |
size(1000) | 1 | only amit |
put("session:neha", 4, 100, 1000) | — | expires at 1100 |
size(1099) | 2 | |
size(1100) | 1 | neha has expired |
time plan
Your 90 minutes
- 10 minclarify — Alive at exactly the expiry time? Does
puton an existing key reset the TTL? Is an expired entry ever evicted instead of a live one? - 15 mindesign — Three questions: find a key (map), least recently used (linked list), what expires next (sorted by expiry). Sketch the node and its pointers.
- 35 mincore code — Plain LRU first: map + doubly linked list, with sentinels. Run the example without TTL. Then add expiry.
- 20 minedge cases — capacity 1, an update, many keys expiring at the same time, an expired key put again.
- 10 minpolish — Small private helpers (
unlink,addFront,remove). Be ready to talk about thread safety.
Practise under real pressure: a 90-minute clock with the phases above. It keeps running if you reload the page.
your turn
Build it here
Write the whole class in the editor. Run replays the example session; Submit adds the hidden tests (edge cases and large random sessions). Stuck for 20 minutes? Open one hint at a time.
Build LruCache in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
The reference, the data-structure reasoning and the rubric are hidden so you can build it first. Even a half-working attempt teaches you more than reading a perfect answer.
Opening all three hints also shows it.
reference
One clean way to build it
A hand-built doubly linked list for recency, a HashMap for lookup, and a TreeSet ordered by expiry for the clean-up.
class LruCache { /** One entry: a node in the recency list and in the expiry order at the same time. */ static class Node { final String key; final long id; // breaks ties between equal expiry times, so the TreeSet never drops a node int value; long expireAt; Node prev, next; Node(String key, long id) { this.key = key; this.id = id; } } private final int capacity; private final Map<String, Node> map = new HashMap<>(); // key → node: O(1) lookup private final Node head = new Node("", -1); // sentinel: head.next is the most recently used private final Node tail = new Node("", -1); // sentinel: tail.prev is the least recently used private final TreeSet<Node> byExpiry = new TreeSet<>( Comparator.comparingLong((Node n) -> n.expireAt).thenComparingLong(n -> n.id)); private long nextId = 0; public LruCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(String key, long now) { Node node = map.get(key); if (node == null) return -1; if (node.expireAt <= now) { // alive only while now < expireAt remove(node); return -1; } unlink(node); // a read is a use: move it to the front addFront(node); return node.value; } public void put(String key, int value, long ttlMs, long now) { purgeExpired(now); // expired entries never take space Node node = map.get(key); if (node == null) { if (map.size() == capacity) remove(tail.prev); // evict the least recently used node = new Node(key, nextId++); map.put(key, node); } else { unlink(node); byExpiry.remove(node); // remove BEFORE changing expireAt, or the TreeSet loses it } node.value = value; node.expireAt = now + ttlMs; byExpiry.add(node); addFront(node); } public int size(long now) { purgeExpired(now); return map.size(); } /** Soonest expiry first: each expired entry costs O(log n) once, then it is gone. */ private void purgeExpired(long now) { while (!byExpiry.isEmpty() && byExpiry.first().expireAt <= now) remove(byExpiry.first()); } private void remove(Node node) { unlink(node); byExpiry.remove(node); map.remove(node.key); } private void unlink(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void addFront(Node node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; }}the choices
Which data structures, and why
HashMap<String, Node>Key → its node, so get finds it at once.
O(1) average.
Recency order: the head side is newest, the tail side is the least recently used. With prev and next, a node unlinks itself.
O(1) to move a node to the front or to drop the last one.
TreeSet<Node> by (expireAt, id)The soonest expiry is always first(), so expired entries are cleared one by one, cheapest first. The id breaks ties so two nodes never look equal.
O(log n) per add/remove; each entry expires once, so clean-up is amortized O(log n) per call.
LinkedHashMap(accessOrder = true)A ready-made map + linked list. Great to mention; many interviewers still want the hand-built list to see that you know how it works.
O(1) per get/put; it does not know about expiry.
self-check
Mark yourself like the interviewer would
Tick only what your code really does. Nothing is saved or sent — this is just for you.
your honest self-score: 0 / 100
traps
Common mistakes
- Scanning every entry to find expired ones. Correct, but O(n) per call — exactly what the interviewer wants you to avoid.
- Changing
expireAtwhile the node is inside theTreeSet. The set is now out of order, andremovecan no longer find the node. - A comparator on
expireAtalone: two nodes with the same expiry look equal, and the set silently keeps only one. - Forgetting to remove a node from all three places (list, map, set). It comes back as a ghost later.
- Evicting a live entry when an expired one could have been dropped instead.
what they ask next
Follow-ups and extensions
Can you avoid the TreeSet?
Yes, with lazy deletion: a PriorityQueue of (expiry, key, version) entries. On clean-up, pop entries and skip the ones whose version is old. The trade-off is memory for stale heap entries.
Or be lazy: check expiry only in get, and scan for an expired entry only when the cache is full. Simpler, but that scan is O(n) in the worst case, and size needs a scan too.
Many threads use the cache.
The simple answer: make the public methods synchronized.
Better throughput: split the cache into shards by key hash, each with its own lock. In real projects, a tested library (Caffeine is a popular Java one) is safer than your own.
Add get that does not change recency (a peek).
Same lookup and expiry check, just skip the move to the front.
How is this different from LeetCode 146?
146 is the map + list part. TTL adds a second order (by time) on the same nodes, and the rule that expired entries are cleared before anything live is evicted.
revise