LRU Cache

By the Syncfusion DevTutorials team · Last updated October 20, 2026

Build a least-recently-used cache with O(1) get and put, using a Map that remembers order, and check it against a speed test.

QuickBite’s menu service takes 200 milliseconds to load a restaurant’s menu. Because many customers view the same popular restaurants, loading those menus repeatedly wastes time.

A cache solves this problem by keeping recently used menus in memory. When a requested menu is already in the cache, the system can return it quickly instead of loading it again.

However, the cache has limited space. When it becomes full, the system must remove one menu before adding another. This case study uses an LRU cache, which removes the item that has not been used for the longest time.

In simple words: you will build a fast, limited-size cache that keeps recently used menus and removes the least recently used menu when it becomes full.

What You Will Learn

In this case study, you will:

1. See why a cache needs a size limit.
2. Understand Least Recently Used (LRU) eviction.
3. Use a Map that remembers order to get O(1) get and put.
4. Measure whether a cache helps with its hit rate.
5. Build the cache in the sandbox and pass the hidden tests, including a speed test.

Step 1: Agree on the Requirements

Before any code, write down what the system must do. In an interview, say these out loud and ask if they are right.

What It Must Do

• new LRUCache(capacity), holding at most capacity entries.
• get(key) returns the value, or undefined, and marks the key as just used.
• put(key, value) adds or updates; when full, it first removes the least recently used key.
• Updating a key does not grow the cache, and marks it as just used.
• Both get and put are O(1).

What We Leave Out

• Expiry by time (that is a TTL cache, practised below).
• Sharing the cache between servers (that is a distributed cache, like Redis).

Leaving things out on purpose is not lazy. It keeps the design small enough to finish, and you can say how you would add them later.

Step 2: Find the Classes

A simple trick: underline the nouns in the requirements. Most of them become classes. The verbs become methods.

Step 3: Build the Key Parts

Why a Limit at All?

A cache keeps answers in memory so the next request is fast. But memory is not free. A cache with no limit grows until the server runs out.

For example, a plain Map that stores a menu for restaurants 1 to 100,000 ends up with 100,000 entries. Nothing ever leaves. A real cache needs a size limit.

Here is the code:

Without a limit, a cache grows forever

const cache = new Map<string, string>();
for (let i = 1; i <= 100000; i++) cache.set("restaurant:" + i, "menu " + i);
console.log("entries:", cache.size);

Expected output:

entries: 100000

Least Recently Used

When the cache is full, something must go. LRU (Least Recently Used) removes the item nobody has asked for in the longest time. Things people use often stay.

The Trick: a Map Remembers Order

The classic answer uses a hash map plus a doubly linked list. In JavaScript, a Map already does both jobs: lookups are O(1), and it remembers the order keys were added.

Step through three keys going into a Map: dosa, idli, vada. The first key is always the oldest:

Here is the same idea in code:

A Map remembers the order keys were added

const m = new Map<string, number>();
m.set("dosa", 1);
m.set("idli", 2);
m.set("vada", 3);
console.log([...m.keys()]);
console.log("oldest:", m.keys().next().value);

Expected output:

[
  "dosa",
  "idli",
  "vada"
]
oldest: dosa

Marking a Key as Just Used

To move a key to the "most recent" end, delete it and set it again.

In the last two steps of the animation, using dosa turns the order dosa, idli, vada into idli, vada, dosa. Now idli is the oldest.

Here is the code:

Delete and set again: the key moves to the end

const m = new Map<string, number>([["dosa", 1], ["idli", 2], ["vada", 3]]);

function touch(key: string): void {
  const v = m.get(key)!;
  m.delete(key);
  m.set(key, v); // now the most recently used
}

touch("dosa");
console.log([...m.keys()]);

Expected output:

[
  "idli",
  "vada",
  "dosa"
]

Removing the Oldest

Step through put on a cache with capacity 2. Putting a, b and then c evicts a and leaves b, c:

Here is the same idea in code:

Evict the oldest when full

const capacity = 2;
const m = new Map<string, string>();

function put(key: string, value: string): void {
  if (m.has(key)) m.delete(key);
  else if (m.size >= capacity) {
    const oldest = m.keys().next().value as string;
    m.delete(oldest);
    console.log("evicted", oldest);
  }
  m.set(key, value);
}

put("a", "1");
put("b", "2");
put("c", "3");
console.log([...m.keys()]);

Expected output:

evicted a
[
  "b",
  "c"
]

Is the Cache Helping?

Count hits (found in the cache) and misses (had to load). A cache with a low hit rate is just using memory.

Step through six requests: r1, r2, r1, r1, r3, r2. The result is 3 hits, 3 misses, a 50% hit rate:

Here is the same idea in code:

Count hits and misses to see if the cache helps

class CountingCache {
  private readonly m = new Map<string, number>();
  hits = 0;
  misses = 0;
  get(key: string, load: () => number): number {
    if (this.m.has(key)) { this.hits++; return this.m.get(key)!; }
    this.misses++;
    const v = load();
    this.m.set(key, v);
    return v;
  }
}

const c = new CountingCache();
for (const id of ["r1", "r2", "r1", "r1", "r3", "r2"]) c.get(id, () => id.length * 100);
console.log(`hits ${c.hits}, misses ${c.misses}, hit rate ${Math.round((c.hits / (c.hits + c.misses)) * 100)}%`);

Expected output:

hits 3, misses 3, hit rate 50%

Lab: Build It

Build LRUCache. The hidden tests check eviction order, updates, and that 400,000 operations finish quickly (so no scanning the whole cache).

Predict the Output

Common Mistakes

Practice

What to Remember

• A cache needs a limit, or it grows forever.
• LRU removes the item unused for the longest time.
• A Map gives O(1) lookups and remembers order.
• Delete and set a key to mark it as just used.
• Check the hit rate to know if the cache helps.

Further Reading

These are the sources used to check this case study:

• MDN: Map: insertion order and O(1) operations.
• Wikipedia: Cache replacement policies: LRU and other eviction rules.
• Redis: Key eviction: how a real cache evicts keys.

Next: Rate Limiter. You will build a class that stops one user from flooding the system.