174: Machine Coding - A Reusable Data Structure
Learning outcomes
- implement a small reusable system from an interface;
- make eviction, expiry, and failure behavior explicit;
- test invariants rather than only examples.
Practice
Build an LRU cache, scheduler, or token-bucket rate limiter. Document capacity, time behavior, duplicate keys, invalid inputs, and complexity. Add tests before optimization.
Checkpoint
Present the public interface, state invariant, complexity, and one rejected alternative. Demonstrate behavior at capacity and after failure.
LRU example
An LRU cache needs a map for lookup and a doubly linked list for recency. The invariant is that the list contains each cached key exactly once, with the most recently used key at the front. get moves a hit to the front; set updates or inserts, then evicts the tail when capacity is exceeded. Both operations should be expected O(1).
Complete solution guidance
Use sentinel head and tail nodes to make insertion and removal uniform. get(key) returns a tagged result such as {found: false} rather than confusing a missing entry with a stored undefined. On update, replace the value and move the existing node to the front. On insertion, link a new node, then evict the tail predecessor if map.size > capacity. Reject non-integer or negative capacities at construction; define capacity zero as “never stores.”
If expiry is required, inject now() and check expiry on read; optionally use lazy deletion plus a cleanup policy. A cache is not a durable source of truth. Document whether it is single-threaded, whether get refreshes expiry, and whether eviction callbacks can fail.
Tests and rubric
Test capacity zero, one-item capacity, hit promotion, miss, update without size growth, eviction order, stored undefined, invalid capacity, expired entries, injected-clock boundaries, and callback failure. Assert map/list cardinality and no duplicate nodes after every operation. Score 3 points each for API/validation, O(1) invariant, eviction/expiry semantics, failure handling, and tests. Reject solutions that claim strict O(1) for an unbounded cleanup scan.
Edge cases
Test capacity zero, replacement of an existing key, repeated reads, invalid capacity, and a value of undefined. Decide whether expiry uses wall-clock time or an injected clock so tests are deterministic.