CSE Roadmap

Core tier · about 4 hours · 6 parts

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.