ProblemsConcurrencyThread-safe LRU cache
AdvancedConcurrency

Thread-safe LRU cache

Context

The backend calls a paid API billed per request. Someone 'optimized' costs with a cache on a global map and not a single lock — now the service crashes under load and the invoice still looks like an inside-job DDoS. Build an LRU cache that survives concurrency: mutex, RAII, and eviction.

Task

Implement a generic ThreadSafeCache<Key, Value> with LRU eviction. It must be safe under concurrent access from multiple threads with no data races.

Constraints

  • Must use std::mutex (or std::shared_mutex for reader optimization)
  • No data races (must pass thread sanitizer)
  • Capacity must be enforced: evict LRU entry when full
  • Must be a template class
  • get must update recency (a get is a "use")

Before you code

  • What is a data race, and why is it undefined behavior?
  • What data structure gives O(1) LRU eviction?
  • When would shared_mutex help versus hurt performance here?

Tests

  • #1Basic put and get
  • #2LRU eviction when over capacity
  • #3Concurrent puts from 4 threads do not crash
  • #4Get returns nullopt for evicted key

Hints

Hint 1

Combine a list for recency order with an unordered_map from key to list iterator for O(1) access.

Hint 2

Lock a std::mutex with lock_guard at the start of every public method.

Hint 3

On get/put, splice the touched node to the front; when over capacity, evict from the back.

Editorthread-safe-cache.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.