← Back
00:00

LRU Cache Provider

Speechify interview questions · Medium · Coding round · 13 tests

Implement createLRUCacheProvider, a bounded cache with three O(1) operations:

  • look up by key
  • mark an entry as recently used
  • evict the least recently used entry

Interface

type CacheProvider<T> = {
  get: (key: string) => T | undefined
  set: (key: string, value: T) => void
  has: (key: string) => boolean
}

createLRUCacheProvider<T>({ ttl, itemLimit }): CacheProvider<T>

Requirements

  1. get(key) returns the value, or undefined if the key is absent or expired.
  2. has(key) returns whether a live (non-expired) entry exists.
  3. set(key, value) inserts or updates.
  4. When itemLimit is exceeded, evict the least recently used entry.
  5. A get counts as a use. A set on an existing key also counts as a use.
  6. ttl (milliseconds, optional): entries older than the ttl behave as if absent. Overwriting a key refreshes its expiry.
  7. If no ttl is given, entries never expire.
  8. All three operations must be O(1). There is a performance test that an O(n) implementation will fail.
Idle