Skip to content
Katabench
Try free

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:

C#
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):

C#
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));

How you're graded

Your suite is run twice over:

  1. Against the correct LruCache above, every one of your tests must pass.
  2. 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

C#
// 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.

C# unit testing exercises →

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