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
get(key)returns the value, orundefinedif the key is absent or expired.has(key)returns whether a live (non-expired) entry exists.set(key, value)inserts or updates.- When
itemLimitis exceeded, evict the least recently used entry. - A
getcounts as a use. Aseton an existing key also counts as a use. ttl(milliseconds, optional): entries older than the ttl behave as if absent. Overwriting a key refreshes its expiry.- If no
ttlis given, entries never expire. - All three operations must be O(1). There is a performance test that an O(n) implementation will fail.
Run your code with Ctrl+Enter to see results.