Build a least-recently-used cache
Implement a fixed-capacity integer cache whose get and put operations evict the least recently used entry when necessary.
Course progress
Problem 87 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
capacity = 2; put(1,10), put(2,20), get(1), put(3,30), get(2), get(3)
Expected output
10 -1 30
What is happening?
Reading key 1 makes key 2 least recent. Inserting key 3 evicts key 2, so the reads return 10, -1, and 30.
Solution strategy
Build the right mental model
Map keys to linked-list nodes for direct lookup and keep the most recently used node at the front of a doubly linked list.
Core concepts
dictionary · linked list
Complexity
Average time O(1) per get or put, space O(capacity).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for lru-cache
using System;
using System.Collections.Generic;
class Program
{
class Entry
{
public int Key { get; private set; }
public int Value { get; set; }
public Entry(int key, int value) { Key = key; Value = value; }
}
class LruCache
{
private readonly int capacity;
private readonly Dictionary<int, LinkedListNode<Entry>> nodes =
new Dictionary<int, LinkedListNode<Entry>>();
private readonly LinkedList<Entry> order = new LinkedList<Entry>();
public LruCache(int capacity) { this.capacity = capacity; }
public int Get(int key)
{
LinkedListNode<Entry> node;
if (!nodes.TryGetValue(key, out node)) return -1;
order.Remove(node);
order.AddFirst(node);
return node.Value.Value;
}
public void Put(int key, int value)
{
LinkedListNode<Entry> node;
if (nodes.TryGetValue(key, out node))
{
node.Value.Value = value;
order.Remove(node);
order.AddFirst(node);
return;
}
if (nodes.Count == capacity)
{
nodes.Remove(order.Last.Value.Key);
order.RemoveLast();
}
node = new LinkedListNode<Entry>(new Entry(key, value));
order.AddFirst(node);
nodes[key] = node;
}
}
static void Main()
{
var cache = new LruCache(2);
cache.Put(1, 10);
cache.Put(2, 20);
Console.Write(cache.Get(1) + " ");
cache.Put(3, 30);
Console.Write(cache.Get(2) + " ");
Console.WriteLine(cache.Get(3));
}
}Knowledge check
Questions students often ask
What is the main idea behind build a least-recently-used cache?
Map keys to linked-list nodes for direct lookup and keep the most recently used node at the front of a doubly linked list.
What is the time and space complexity of this solution?
Average time O(1) per get or put, space O(capacity).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.