Implement an LRU cache with explicit updates

Clarify the observable contract

An LRU cache evicts the least recently used entry when inserting a new key into a full cache. Both a successful read and an update count as use; a failed read does not. Capacity must be positive, keys use ordinal equality and the printed order is most recent first. This is a single-owner in-memory cache, without expiration, byte accounting or concurrent access.

Maintain a bijection between dictionary keys and linked-list nodes. Each stored key appears exactly once in the list, and each list node has exactly one dictionary entry pointing to that same node. Recency belongs to the list; the dictionary is an index for finding the node efficiently.

Walk through the verified program

After inserting a and b, reading a moves it to the front. Inserting c then evicts b. Updating a to nine changes the existing node rather than creating a second entry; the order becomes a,c. The final read retrieves nine. The Boolean miss return keeps a missing value distinct from a stored zero.

Updating a calls Remove with the node already retrieved from the dictionary, then AddFirst with that same node. Its identity remains stable while its payload changes. A failed lookup of b returns false without moving another entry, and retrieving a zero value would still return true for an existing node.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var cache = new Lru(2); cache.Put("a", 1); cache.Put("b", 2); cache.TryGet("a", out _); cache.Put("c", 3);
Console.WriteLine("b present:" + cache.TryGet("b", out _).ToString().ToLowerInvariant());
cache.Put("a", 9); Console.WriteLine("order:" + cache.Keys()); cache.TryGet("a", out int value); Console.WriteLine("a:" + value);
sealed class Lru {
    private readonly int capacity; private readonly LinkedList<(string Key,int Value)> order = new();
    private readonly Dictionary<string,LinkedListNode<(string Key,int Value)>> map = new(StringComparer.Ordinal);
    public Lru(int capacity) { if (capacity <= 0) throw new ArgumentOutOfRangeException(nameof(capacity)); this.capacity = capacity; }
    public void Put(string key, int value) { if (map.TryGetValue(key, out var node)) { node.Value = (key,value); order.Remove(node); order.AddFirst(node); return; }
        if (map.Count == capacity) { var old = order.Last!; map.Remove(old.Value.Key); order.RemoveLast(); }
        map.Add(key, order.AddFirst((key,value))); }
    public bool TryGet(string key, out int value) { if (!map.TryGetValue(key,out var node)) { value=0; return false; } order.Remove(node); order.AddFirst(node); value=node.Value.Value; return true; }
    public string Keys() => string.Join(",",order.Select(x=>x.Key));
}

Account for time, storage and allocations

A dictionary points directly to linked-list nodes, so lookup, unlinking and moving a known node require expected constant time. Insertion can allocate a node and dictionary growth can resize storage. Space is O(capacity) entries, but that entry bound is not a bound on key bytes or total process memory.

Expected constant-time operations rely on ordinary dictionary behavior and direct node references. Linked-list nodes, dictionary buckets and retained key strings contribute overhead beyond the integer values. Reporting a capacity of two describes entry count, not two allocations or a precise memory ceiling.

Review assumptions and likely defects

Calling LinkedList.Remove by value would search, losing the intended constant-time move. Failing to remove an evicted key from the dictionary breaks the two-structure invariant. Enumeration order of the dictionary is irrelevant because the list defines recency. Shared access would require synchronization around both structures together.

An eviction must remove from both structures before the new key becomes visible. Under concurrent access a lock would need to cover the whole compound transition, including the recency move on a hit. Replacing the dictionary with a concurrent dictionary alone would not make the linked-list invariant safe.

Practice one: discriminate edge cases

Test capacity one, updating an existing key, a missing read and storing zero. Hint: updates should not evict an unrelated key or increase the count. After each operation compare the dictionary membership with the keys in the recency list.

Use a sequence where an update changes the next victim: insert a,b; update a; insert c; then assert b is absent. Separately test a miss followed by insertion to prove a failed read did not affect order. These scenarios discriminate real LRU behavior from insertion-order eviction.

Practice two: defend an extension

Design a byte-bounded cache with expiration and concurrent callers. Decide whether hits update recency under one lock, whether oversized values are rejected and whether expiration is checked lazily. State which guarantees you would simplify rather than claiming the small cache already provides them.

A practical shared cache could begin with one lock and an entry-size admission check, then add expiration according to a documented clock. Oversized values should be rejected before evicting useful entries unless another policy is explicitly intended. Coarser synchronization may be an acceptable correctness-first choice until measurements justify more complex partitioning.

Evaluate correctness and interview reasoning

An interview review should trace one hit, one update, one miss and one eviction, showing both data structures after every step. It should explain why moving a known node is constant-time and why searching for a value is not equivalent. A senior answer names missing requirements such as TTL, byte bounds, synchronization and process lifetime without pretending the small cache already implements them. Independent tests should target the dictionary/list bijection as well as returned values. The important achievement is an explicit invariant across two mutable structures, not merely choosing two familiar collection classes.