Coding interviews
Reveal answer and reasoning
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.
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. 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 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.
What a strong answer covers
- A practical shared cache could begin with one lock and an entry-size admission check, then add expiration according to a documented clock.
- A dictionary points directly to linked-list nodes, so lookup, unlinking and moving a known node require expected constant time.
- Calling LinkedList.Remove by value would search, losing the intended constant-time move.
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.