Katkat
Back

Object-oriented design of a fixed-capacity LRU cache with O(1) get and put

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

An object-oriented design question that asks for a fixed-capacity least-recently-used cache whose get and put operations run in constant average time and evict the least recently used entry when the cache is full. It tests class decomposition, data structure choice, recency bookkeeping, edge cases and awareness of thread safety.

In an object-oriented design round, design and implement a least-recently-used (LRU) cache with a fixed capacity:

  • get(key) returns the value stored under key and marks the key as the most recently used. If the key is not in the cache, it reports a miss.
  • put(key, value) inserts the key, or updates its value if it is already present, and marks it as the most recently used. If an insert makes the cache exceed its capacity, the least recently used key is evicted.

Present the design the way an object-oriented round expects: the classes, what each one is responsible for, and their public interfaces, then implement them. Both operations are expected to run in constant average time, which is the usual expectation for this exercise; confirm it with the interviewer.

Constraints and Clarifications

  • The capacity is fixed when the cache is created.
  • One process, data in memory.
  • Keys are hashable; values are arbitrary objects.

Clarifying Questions

  • How should get report a miss: a sentinel such as -1, None, or an exception? Can a stored value itself be None?
  • Does updating an existing key count as a use, and can an update ever cause an eviction?
  • What should a capacity of zero or less mean: an error, or a cache that stores nothing?
  • Will several threads share the cache?
  • May I use a built-in ordered map, or should the recency structure be written by hand?

Hints

Hint 1

One structure is not enough: A hash map finds a key in constant time but knows nothing about recency. Think about what second structure can move any entry to the most-recent end, and remove the entry at the least-recent end, in constant time.

Hint 2

Name the responsibilities: Separate what the cache promises to its callers from how it tracks recency, and decide which class owns each piece of state.

Follow-up questions

  • Make the cache safe for many threads. Why does a read-write lock not help much here, and how would sharding change the guarantees?
  • Switch the eviction policy to least-frequently-used without changing the callers. What in your design changes?
  • Bound the cache by the total size of its values instead of the number of entries.
  • Add an expiry time per entry. How does it interact with the recency order?