Find Bugs in an LRU Cache
Find Bugs in an LRU Cache
A Java LRUCache class is provided, intended to implement a least-recently-used cache with a fixed capacity. A successful get operation and every put operation should mark the accessed key as the most recently used. When a new key is inserted and the cache is at capacity, the least recently used key should be evicted.
Analyze the provided Java code for the LRUCache class. Identify all behaviors that violate the specified requirements. For each distinct defect, provide a minimal failing test case. Propose a corrected implementation that addresses all identified issues. Explain the ordering mode used by LinkedHashMap and why simply compiling the code is insufficient to guarantee correct recency semantics.
Constraints & Assumptions:
- Capacity is a positive integer.
- Keys are integers and values are non-null strings.
getshould returnnullfor a key miss and should not alter the cache's order.- The expected time complexity for
getandputoperations is constant on average.
Clarifying Questions to Ask:
- Should zero capacity be rejected or treated as a cache that stores nothing?
- Is the implementation required to be thread-safe?
- May library-provided access ordering and eviction hooks be used?
- Should updating an existing value count as an access that makes it most recently used? (The specification implies yes.)
AI interview prep
Core dilemma
Correctly implementing LRU eviction and recency updates using a standard library data structure, specifically understanding the nuances of `LinkedHashMap`'s ordering and eviction mechanisms beyond basic usage.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Find Bugs in an LRU Cache
Find Bugs in an LRU Cache
A Java LRUCache class is provided, intended to implement a least-recently-used cache with a fixed capacity. A successful get operation and every put operation should mark the accessed key as the most recently used. When a new key is inserted and the cache is at capacity, the least recently used key should be evicted.
Analyze the provided Java code for the LRUCache class. Identify all behaviors that violate the specified requirements. For each distinct defect, provide a minimal failing test case. Propose a corrected implementation that addresses all identified issues. Explain the ordering mode used by LinkedHashMap and why simply compiling the code is insufficient to guarantee correct recency semantics.
Constraints & Assumptions:
- Capacity is a positive integer.
- Keys are integers and values are non-null strings.
getshould returnnullfor a key miss and should not alter the cache's order.- The expected time complexity for
getandputoperations is constant on average.
Clarifying Questions to Ask:
- Should zero capacity be rejected or treated as a cache that stores nothing?
- Is the implementation required to be thread-safe?
- May library-provided access ordering and eviction hooks be used?
- Should updating an existing value count as an access that makes it most recently used? (The specification implies yes.)