Build an LRU Cache

Difficulty: Medium · Category: Cache · Languages: Java 17, Python 3.11, Go 1.22, Node.js 20, TypeScript 5.x

LRU Cache

Background

Caches are everywhere — from CPU L1/L2 caches to CDN edge caches to application-level in-memory stores. A cache with a Least Recently Used (LRU) eviction policy discards the entry that hasn't been accessed for the longest time when space runs out. This is one of the most commonly asked system design and low-level design interview questions.

Your Task

Implement the LRUCacheContract interface backed by the provided KV Store. Your implementation must:

Use the KV Store for underlying data storage.
All core operations (get, put, remove) must run in O(1) amortised time.
get and put must update an entry's recency. containsKey must not.
When the cache is full and a new key is inserted, the least recently used entry must be evicted.

Recommended infrastructure: kv-store — in-memory KV store provides the O(1) access needed for cache operations.

How It Works

The platform injects your chosen infrastructure SDK(s) via constructor. For example, if you select KV Store:

public class MyLRUCache implements LRUCacheContract {
    private final KVStoreClient store;

    public MyLRUCache(KVStoreClient store) {
        this.store = store;
    }

    // ... implement methods using store.*
}

See the SDK Docs tab for the full API reference of your chosen system.

Interface

public interface LRUCacheContract {
    void init(int capacity);
    String get(String key);
    void put(String key, String value);
    boolean remove(String key);
    int size();
    boolean containsKey(String key);
}

Method Details

Method	Description
`init`	Set the maximum capacity. Called once before any other method.
`get`	Return the value for the key (or `null`). Marks the key as recently used.
`put`	Insert or update a key-value pair. If at capacity with a new key, evict the LRU item first. Marks the key as recently used.
`remove`	Remove the key. Returns `true` if the key existed.
`size`	Return the current number of entries (never exceeds capacity).
`containsKey`	Check existence without affecting recency order.

Constraints

capacity ≥ 1
Keys and values are non-null strings
The cache will be tested with capacities up to 10 000
Performance target: ≥ 50 000 ops/sec with p99 latency ≤ 1 ms

Examples

init(3)

put("a", "1")             size → 1
put("b", "2")             size → 2
put("c", "3")             size → 3

get("a")                  → "1"   (a is now most-recently used)

put("d", "4")             // Evicts "b" (LRU). size → 3
get("b")                  → null

containsKey("c")          → true   (does NOT affect recency)
put("e", "5")             // Evicts "c" (LRU, because containsKey didn't promote it)
get("c")                  → null

remove("d")               → true.  size → 2

Hints

The classic O(1) approach uses a HashMap + Doubly-Linked List. The map provides O(1) lookup; the linked list maintains recency order with O(1) move-to-front and remove-from-tail.
Java's LinkedHashMap with access-order can serve as inspiration, but your implementation must use the provided KV Store.
For thread safety, consider a ReadWriteLock or fine-grained synchronisation.
Remember that containsKey must not promote the entry — be careful if your data structure automatically reorders on access.

Infrastructure your code runs against

Key-Value Store

How your solution is graded

Your score combines functional correctness (40%), performance (40%) and code quality (20%).

Target throughput: 50,000 operations/second
Target p99 latency: 1 ms
Load test concurrency: 4 concurrent clients
Load test duration: 10 seconds
Maximum error rate: 0.1%