Write a simple fixed-capacity LRU cache in C#.

Capacity 2: put A, put B, get A, put C. Key B is evicted because A was recently used and C is new.

• Capacity must be positive.
• Get moves an existing key to most recently used.
• Put existing key updates value and moves it to most recently used.
• Put new key over capacity evicts least recently used.

I would combine a dictionary for O(1) key lookup with a linked list for recency order. The front of the list is most recent and the back is least recent. The dictionary maps keys to linked-list nodes. On get or update, I move the node to the front. On insert over capacity, I remove the last node and remove its key from the dictionary.

public sealed class LruCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<Entry>> _nodes = new();
    private readonly LinkedList<Entry> _order = new();

    public LruCache(int capacity)
    {
        if (capacity <= 0) throw new ArgumentOutOfRangeException(nameof(capacity));
        _capacity = capacity;
    }

    public bool TryGet(TKey key, out TValue value)
    {
        if (!_nodes.TryGetValue(key, out var node))
        {
            value = default!;
            return false;
        }

        _order.Remove(node);
        _order.AddFirst(node);
        value = node.Value.Value;
        return true;
    }

    public void Put(TKey key, TValue value)
    {
        if (_nodes.TryGetValue(key, out var existing))
        {
            existing.Value = new Entry(key, value);
            _order.Remove(existing);
            _order.AddFirst(existing);
            return;
        }

        var node = new LinkedListNode<Entry>(new Entry(key, value));
        _order.AddFirst(node);
        _nodes[key] = node;

        if (_nodes.Count > _capacity)
        {
            var last = _order.Last!;
            _order.RemoveLast();
            _nodes.Remove(last.Value.Key);
        }
    }

    private sealed record Entry(TKey Key, TValue Value);
}

Get and put are O(1) average time because dictionary lookup and linked-list node moves are constant time. Space is O(capacity).

• Capacity of 1.
• Get missing key.
• Put existing key.
• Evict after a get changed recency.
• Reference or nullable values depending on TValue.

• Use capacity 1 to catch eviction mistakes.
• Update an existing key and verify count does not grow.
• Get a key before inserting another to verify recency updates.

• Using only a list and making get O(n).
• Forgetting to remove evicted keys from the dictionary.
• Not moving keys on get.
• Growing beyond capacity when updating existing keys.