Implement an LRU Cache

Quick Overview

Implement an LRU cache with constant-time lookup, recency updates, and eviction, including existing-key updates, zero capacity, and concurrency pitfalls.

Implement an LRU Cache

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a cache of fixed capacity with `get(key)` and `put(key, value)`. A successful get and any insertion or update make that key most recently used. When inserting a new key into a full cache, evict the least recently used key. Return `-1` for a missing key. ### Constraints & Assumptions Use the standard LRU formulation. Capacity is nonnegative; a zero-capacity cache stores nothing. Target average O(1) time per operation. ### Clarifying Questions to Ask - Does updating an existing key refresh its recency? - Can a stored value be `-1`, and would a distinct missing-value result be preferable in a production interface? ```hint Two forms of access You need both direct key lookup and constant-time movement within a recency order. ``` ### What a Strong Answer Covers - A hash index paired with a mutable recency order. - Existing-key updates, hit promotion, and eviction of the correct endpoint. - Consistent removal from both structures and behavior at capacity zero. ### Follow-up Questions - How would concurrent gets and puts preserve a single recency order? - How would time-based expiration interact with least-recently-used eviction?

Overview: Implement an LRU cache with constant-time lookup, recency updates, and eviction, including existing-key updates, zero capacity, and concurrency pitfalls.

Read the full Amazon Software Engineer interview experience this question came from

Amazon logo
Amazon
Nov 18, 2026
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Implement a cache of fixed capacity with get(key) and put(key, value). A successful get and any insertion or update make that key most recently used. When inserting a new key into a full cache, evict the least recently used key. Return -1 for a missing key.

Constraints & Assumptions

Use the standard LRU formulation. Capacity is nonnegative; a zero-capacity cache stores nothing. Target average O(1) time per operation.

Clarifying Questions to Ask Guidance

  • Does updating an existing key refresh its recency?
  • Can a stored value be -1 , and would a distinct missing-value result be preferable in a production interface?

What a Strong Answer Covers Guidance

  • A hash index paired with a mutable recency order.
  • Existing-key updates, hit promotion, and eviction of the correct endpoint.
  • Consistent removal from both structures and behavior at capacity zero.

Follow-up Questions Guidance

  • How would concurrent gets and puts preserve a single recency order?
  • How would time-based expiration interact with least-recently-used eviction?