Katkat
Back

Implement an LRU cache

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates competency in data structure design and algorithmic complexity by requiring a bounded key-value cache with O(1) average-time get and put operations.

Design a key-value cache with a fixed capacity. It must support:

  • get(key): return the value for the key if it exists, otherwise return -1.
  • put(key, value): insert or update the key. If the cache is full, evict the least recently used key before inserting the new one.

Both operations should run in O(1) average time.