Flight Fare Cache

HarddesignAlso known as LRU Cache with TTL

A travel site shows fares that come from slow airline APIs, so it caches each quote in memory. Two rules fight over the cache. A fare goes stale after a few minutes, so every entry has a time to live and must not be served after it runs out. And memory is limited, so when the cache is full the entry nobody has used for the longest goes first. An entry that has already expired should never push out one that is still good.

This is the in-memory cache from Caching, with TTL expiry and least-recently-used eviction, the same pair of rules an in-memory cache server such as Redis can be configured to apply (real servers approximate LRU to save memory).

Your task

Write a class FareCache. An entry stored at time s with time to live ttlMs expires at s + ttlMs: from then on it is treated as if it were not in the cache at all, and it takes no space.

constructor(capacity): at most capacity unexpired entries.
get(route, t): if route has an unexpired entry, return its fare and mark it as just used. Otherwise return -1.
put(route, fare, ttlMs, t): store the fare with a new expiry time and mark it as just used. If route already has an unexpired entry, replace it. If not, and the cache already holds capacity unexpired entries, first remove the one that was used least recently (by get or put).
size(t): return the number of unexpired entries.

class FareCache

Examples

Example 1

Input

new FareCache(2)
.put("LHR-JFK", 420, 5000, 0)
.put("CDG-NRT", 880, 5000, 100)
.get("LHR-JFK", 200)
.put("SFO-SYD", 1100, 5000, 300)
.get("CDG-NRT", 400)
.get("SFO-SYD", 400)
.size(400)

Output

[null, null, null, 420, null, -1, 1100, 2]

Why

Nothing expires before 5,000 here, so this is plain LRU. Reading LHR-JFK at 200 makes it the most recently used, which leaves CDG-NRT as the least recently used. The cache is full when SFO-SYD arrives, so CDG-NRT is evicted. The cache now holds LHR-JFK and SFO-SYD.

Example 2

Input

new FareCache(2)
.put("A", 1, 100, 0)
.put("B", 2, 1000, 10)
.get("A", 50)
.put("C", 3, 1000, 150)
.get("B", 160)
.get("A", 160)
.size(160)

Output

[null, null, null, 1, null, 2, -1, 2]

Why

After the read at 50, B is the least recently used. But A expired at 0 + 100 = 100, so at 150 the cache holds only B, and C fits without evicting anything. A cache that let A keep its slot until something pushed it out would have evicted B, the one fare still worth keeping.

Constraints

1 ≤ capacity ≤ 1,000
1 ≤ ttlMs ≤ 1,000,000,000
1 ≤ fare ≤ 1,000,000
0 ≤ t ≤ 1,000,000,000,000, and t never decreases from one call to the next
Routes are non-empty strings of up to 20 characters
At most 3,000 calls per test

Start with brute force

Store entries in a plain list with a "last used" time, and on every call scan the list to drop expired entries, find a route, or find the least recently used. Each call is O(n), so 3,000 calls on a cache of 1,000 entries is about 3 million steps here, and a real cache with a million entries serving thousands of reads a second cannot afford a full scan per read.

The ordered map makes the LRU part O(1), and the heap finds expired entries in order of expiry, so each entry is removed once, in O(log n).

Hints

0 of 4 shown

Hint 1
Ignore expiry for a moment. Which operations does plain LRU need to be O(1): find an entry by key, mark it as just used, and find the least recently used one? Which structure keeps entries in order of use?
Hint 2
An insertion-ordered map does all three: Map in JavaScript or OrderedDict in Python. Delete and re-insert (or move_to_end) to mark a use; the first key is the least recently used.
Hint 3
Now expiry. If you remove every expired entry at the start of each call, then get, put and size only ever see unexpired entries, and the LRU logic does not change. How do you find the expired ones without scanning the whole cache?
Hint 4
Keep a min-heap of (expiresAt, route). At the start of each call, pop while the top's expiresAt ≤ t, and delete the route only if its current entry still has that same expiry; an older heap item for a route that was put again is just skipped.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Split the problem in two. An insertion-ordered map handles LRU: each use moves a route to the end, so the front is always the least recently used. A min-heap of expiry times handles TTL: at the start of every call, pop everything that has expired. After that purge, the map holds only unexpired entries, so "full" and "least recently used" mean exactly what the task says.

Trace the second example, capacity 2:

put(A, 1, 100, 0): map [A], heap [(100, A)].
put(B, 2, 1000, 10): map [A, B], heap [(100, A), (1010, B)].
get(A, 50): nothing has expired (100 > 50). A moves to the end: map [B, A]. Return 1.
put(C, 3, 1000, 150): purge pops (100, A), and A's entry still expires at 100, so it is deleted: map [B]. One entry, capacity 2, so C goes in without evicting: map [B, C].
get(B, 160) returns 2, get(A, 160) returns -1, size(160) is 2.

The check expiresAt === at is what makes the lazy heap safe. When a route is put again, its old heap item stays behind; when that item reaches the top, the route's current entry has a different expiry, so it is not deleted. Many cache servers make a similar trade: they expire keys lazily when touched, plus a background sweep, rather than running a timer per key.

Reference solution

class FareCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.entries = new Map(); // route -> { fare, expiresAt }, least recently used first
    this.expiry = new MinHeap(); // [expiresAt, route], may hold outdated items
  }
 
  purge(t) { // drop every entry that has expired by time t
    while (this.expiry.size() && this.expiry.top()[0] <= t) {
      const [at, route] = this.expiry.pop();
      const e = this.entries.get(route);
      if (e && e.expiresAt === at) this.entries.delete(route); // skip outdated items
    }
  }
 
  get(route, t) {
    this.purge(t);
    const e = this.entries.get(route);
    if (!e) return -1;
    this.entries.delete(route);  // re-insert to mark as just used
    this.entries.set(route, e);
    return e.fare;
  }
 
  put(route, fare, ttlMs, t) {
    this.purge(t);
    if (this.entries.has(route)) this.entries.delete(route);
    else if (this.entries.size === this.capacity) {
      this.entries.delete(this.entries.keys().next().value); // least recently used
    }
    this.entries.set(route, { fare, expiresAt: t + ttlMs });
    this.expiry.push([t + ttlMs, route]);
  }
 
  size(t) {
    this.purge(t);
    return this.entries.size;
  }
}
 
class MinHeap { // ordered by item[0]
  constructor() { this.a = []; }
  size() { return this.a.length; }
  top() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    for (let i = a.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      for (let i = 0; ; ) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

import heapq
from collections import OrderedDict
 
 
class FareCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.entries = OrderedDict()  # route -> (fare, expires_at), least recently used first
        self.expiry = []  # heap of (expires_at, route), may hold outdated items
 
    def _purge(self, t):  # drop every entry that has expired by time t
        while self.expiry and self.expiry[0][0] <= t:
            at, route = heapq.heappop(self.expiry)
            e = self.entries.get(route)
            if e is not None and e[1] == at:  # skip outdated items
                del self.entries[route]
 
    def get(self, route, t):
        self._purge(t)
        e = self.entries.get(route)
        if e is None:
            return -1
        self.entries.move_to_end(route)  # mark as just used
        return e[0]
 
    def put(self, route, fare, ttl_ms, t):
        self._purge(t)
        if route in self.entries:
            del self.entries[route]
        elif len(self.entries) == self.capacity:
            self.entries.popitem(last=False)  # least recently used
        self.entries[route] = (fare, t + ttl_ms)
        heapq.heappush(self.expiry, (t + ttl_ms, route))
 
    def size(self, t):
        self._purge(t)
        return len(self.entries)

TimeO(log n)Amortized per call: map operations are O(1), and each heap item is pushed once and popped at most once, at O(log n) each, where n is the number of heap items.

SpaceO(n)The map holds at most capacity entries; the heap holds one item per put until it is popped.

Learn the idea: Caching

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code