Katkat
Back

Implement a Least-Recently-Used Cache

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design and implement an efficient in-memory cache with eviction behavior, testing understanding of data structure selection, state management, and time/space complexity under capacity constraints.

Design and implement an in-memory least-recently-used cache.

Requirements:

  • The cache is initialized with a positive integer capacity.
  • Implement get(key): return the value associated with key if it exists; otherwise return -1 or null.
  • Implement put(key, value): insert or update the value for key.
  • Any successful get or put makes that key the most recently used item.
  • If inserting a new key causes the cache to exceed capacity, evict the least recently used key.
  • Both get and put should run in O(1) average time.

Explain your data structures, edge cases, and time/space complexity.