HomeChallengesRepsProblemsLeaderboardTake a challenge

An LRU Cache

Search results get refetched every keystroke. Cache them — but a cache with no eviction is a memory leak with good intentions.

Intermediate20 min on the clock5 graded checks · 100 pointsData Structures at Work
Graded by running your code against real cases.

What you build

  • createCache(max) returning get, set, a size property and keys()
  • get returns undefined for a key that was never set
  • When size passes max, drop the LEAST RECENTLY USED entry
  • Reading a key must count as using it
  • Setting an existing key updates it without growing the cache

Done means

A key you just read survives the next eviction, and one you have not touched does not.

How it is graded

Published in full, before you start — every point is one of these and there is nothing else. Each one runs your code; it is not a search for keywords.

  1. get and set work, and a miss is undefined+20Caching and eviction
  2. It evicts once it is full+25Caching and eviction
  3. Reading a key protects it+25Caching and eviction
  4. Setting an existing key does not grow it+15Caching and eviction
  5. It never exceeds max+15Caching and eviction

What it teaches

The rest of Data Structures at Work