Coding interviews
Reveal answer and reasoning
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.
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.
What a strong answer covers
- An LRU cache evicts the least recently used entry when inserting a new key into a full cache.
- Updating a calls Remove with the node already retrieved from the dictionary, then AddFirst with that same node.
- A dictionary points directly to linked-list nodes, so lookup, unlinking and moving a known node require expected constant time.
Common pitfall
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.
Follow-up questions
- 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.
- How would capacity zero differ from a cache entry whose stored value is zero?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.