Part 6 of 6 · 3 min read
Exercises
Easy
Easy 1: Trace by hand (20 minutes)
With capacity 3, trace the cache order after: put 1, put 2, put 3, get 1, put 4, get 3, put 5.
Done when: you write the order after each step and name the key evicted at each overflow (2, then 1).
Hint
The most recently used key is always at the front.
Easy 2: Run the cache (20 minutes)
Type LruCache and reproduce the capacity-2 run table.
Done when: it prints the order [c, a] and one hit and one miss.
Hint
Print the keys by walking from head.next to tail.
Easy 3: Cost table (20 minutes)
Make a table of the cost of get and put for four designs: map only, list only, map plus singly linked list, and map plus doubly linked list.
Done when: four rows give the cost and a one-line reason each.
Hint
Moving a node in a singly linked list needs its previous node, which costs a walk.
Medium
Medium 1: LinkedHashMap version (45 minutes)
Build the same cache with LinkedHashMap in access-order mode. Run the same tests.
Done when: all tests that passed before pass again, and a note compares lines of code.
Hint
The constructor takes true for access order, and removeEldestEntry returns true when the size exceeds capacity.
Medium 2: Expiry (45 minutes)
Add a time-to-live per entry with an injected clock. An expired entry counts as a miss and is removed.
Done when: a test moves the clock past the limit and the entry is gone.
Hint
Store the expiry time in the node.
Medium 3: Policy comparison (45 minutes)
Run the three policies on a list of 1,000 requests where a few keys are very popular. Report the hit rate of each.
Done when: a table lists three hit rates and a sentence explains the winner.
Hint
Use a seeded random generator to make a skewed list.
Hard
Hard 1: Constant-time LFU (90 minutes)
Write a least-frequently-used cache with constant-time operations. Keep a map from key to count, and a map from count to an ordered set of keys, and track the minimum count.
Done when: a test with 100,000 operations runs fast, and ties are broken by oldest use.
Hint
When a key's count goes from n to n + 1, move it between the two sets.
Hard 2: Sharded cache (90 minutes)
Build a cache of 16 shards, each its own LruCache, chosen by key hash. Compare throughput with one lock on 8 threads.
Done when: a table shows operations per second for both, and a sentence states what the sharded version gives up.
Hint
Math.floorMod(key.hashCode(), 16) picks the shard.
Hard 3: Loader with eviction (90 minutes)
Combine the future-based loader with a bounded LRU map. Make sure a failed load is removed and an evicted key is loaded again when asked.
Done when: eight threads on one key load once, a failure is retried, and an evicted key triggers a new load.
Hint
Remove the future when it fails, and when the key is evicted.