Test the LRU Cache
Hard About 30 min Free, no account needed
You're given a correct LRU cache. Write the call sequences that prove it evicts the least-recently-used entry.
The brief
An LRU (least-recently-used) cache keeps the most-recently-touched entries and evicts the stalest one when it runs out of room. The cache here is already written and correct. Your job is to write the tests that prove it, which means designing the call sequences that expose the eviction order.
Here is the code under test:
public class LruCache
{
public LruCache(int capacity) { ... }
// Returns the value for key, or -1 if absent. A successful read counts as a use.
public int Get(int key) { ... }
// Inserts or updates key. When full, the least-recently-used entry is evicted.
public void Put(int key, int value) { ... }
}A read (Get) and an overwrite (Put of an existing key) both refresh that key's recency.
Write a Tests class. Each public, parameterless method is one test: it passes if it runs
without throwing and fails when an assertion throws. Build a cache, drive a sequence of operations,
then assert. A tiny assertion library is in scope (no using needed):
Assert.True(condition); Assert.False(condition);
Assert.Equal(expected, actual); Assert.NotEqual(a, b);
Assert.Null(x); Assert.NotNull(x);
Assert.Throws<SomeException>(() => ...);
var cache = new LruCache(2);
cache.Put(1, 1);
Assert.Equal(1, cache.Get(1));Your suite is run twice over:
- Against the correct
LruCacheabove, every one of your tests must pass. - Against a set of planted-bug "mutants", broken caches you never see. A mutant is caught when at least one of your tests fails against it.
You pass when your suite is green on the correct code and catches at least 5 of the 6 mutants. The mutants forget that a Get refreshes recency, evict the wrong entry, never evict at all, hold one item too many, or return 0 for a miss. A single Put/Get catches none of the eviction bugs. Design sequences that fix which key is least-recently-used, then assert what survives. Stuck? Reveal the model suite to see what thorough looks like.
Starter code
// Write tests for the `LruCache` class. Each public, parameterless method is one test; it passes
// if it doesn't throw. Make your suite pass on the correct code AND catch the hidden buggy versions.
// A single Put/Get proves nothing. The behavior lives in which entry gets evicted, and when.
public class Tests
{
public void A_stored_value_can_be_read_back()
{
var cache = new LruCache(2);
cache.Put(1, 1);
Assert.Equal(1, cache.Get(1));
}
// TODO: drive sequences of Put/Get that force an eviction and prove the RIGHT key is dropped.
}How it is graded
You write the tests. A suite passes only when it stays green on correct code and turns enough faulty implementations red.
What it practices
- Stateful testing
- Drive call sequences and state-machine transitions, not just single calls.
- Mutation testing
- Write tests strong enough to catch planted bugs, not just to pass.
Related katas
- Test the Sliding-Window Rate Limiter Hard Free You're given a correct sliding-window rate limiter. Write the call sequences that prove the window slides and the limit holds.
- Test the Transfer Ledger Hard Free You're given a correct transfer ledger. Write stateful tests that prove transfers are atomic and idempotent.
- Test the Bowling Scorer Hard Free You're given a correct ten-pin bowling scorer. Write the tests that exercise spares, strikes, and the bonus rolls.
- Test the Circuit Breaker State Machine Hard Free Drive closed, open, and half-open transitions with a fake clock and prove rejected calls never execute.