Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Implement LRU cache with O(1) ops states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement LRU cache with O(1) ops

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design and implement a fixed-capacity cache supporting get(key) -> value and put(key, value) in O( 1) average time. When capacity is reached, evict the least recently used entry. Specify how recency is updated on get and put, how updates to existing keys are handled, what to return for missing keys, and discuss thread-safety options and testing strategy.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Implement LRU cache with O(1) ops states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Design and implement a fixed-capacity Least Recently Used (LRU) cache that supports two operations in O(1) average time: - `put(key, value)` — insert or update a key. If the key already exists, overwrite its value and mark it as most recently used. If inserting a new key would exceed the cache capacity, first evict the least recently used entry. - `get(key)` — return the value for `key` if it is present (and mark it most recently used), otherwise return `-1`. Because a cache is stateful and operations are interdependent, this challenge gives you the whole operation stream up front so your solution is deterministically testable. Implement a function `solution(capacity, operations)` where: - `capacity` is a positive integer — the maximum number of key/value pairs the cache may hold. - `operations` is a list of operations applied in order. Each operation is one of: - `["put", key, value]` - `["get", key]` Return a list with one entry per operation, in order: - For each `put`, append `null` (Python `None`). - For each `get`, append the looked-up value, or `-1` if the key is absent. Recency rules: - A successful `get` makes that key the most recently used. - A `put` (whether it inserts a new key or updates an existing one) makes that key the most recently used. - Eviction removes the single least recently used key, and only happens when a new insertion pushes the size past `capacity`. The intended O(1) design pairs a hash map (key → node) with a doubly linked list ordered by recency (head = most recent, tail = least recent). The hash map gives O(1) lookup; the linked list gives O(1) move-to-front and O(1) tail eviction. Python's `OrderedDict` provides the same guarantees via `move_to_end` and `popitem(last=False)`.

Constraints

  • 1 <= capacity <= 10^4
  • 0 <= number of operations <= 10^5
  • Keys and values are integers in the range -10^9 .. 10^9
  • Each 'put' has the form ["put", key, value]; each 'get' has the form ["get", key]
  • get on a missing key returns -1 (values are otherwise valid integers, including negative ones)

Examples

Input: (2, [['put', 1, 1], ['put', 2, 2], ['get', 1], ['put', 3, 3], ['get', 2], ['put', 4, 4], ['get', 1], ['get', 3], ['get', 4]])

Expected Output: [None, None, 1, None, -1, None, -1, 3, 4]

Explanation: Capacity 2, the canonical LRU trace. put(1,1) and put(2,2) fill the cache. get(1)=1 makes 1 most recent (order now: 1 newest, 2 oldest). put(3,3) overflows and evicts the LRU key 2. get(2)=-1 (evicted). put(4,4) evicts the now-LRU key 1. get(1)=-1, get(3)=3, get(4)=4.

Input: (1, [['put', 2, 1], ['get', 2], ['put', 3, 2], ['get', 2], ['get', 3]])

Expected Output: [None, 1, None, -1, 2]

Explanation: Capacity 1 edge case. put(2,1) then get(2)=1. put(3,2) must evict key 2 because only one slot exists, so get(2)=-1 and get(3)=2.

Hints

  1. You need two things at once: O(1) lookup by key, and O(1) knowledge of which key is least recently used. A hash map alone gives you the first but not the second.
  2. Pair a hash map (key -> node) with a doubly linked list ordered by recency: head = most recently used, tail = least recently used. On any access, splice the node to the head; to evict, remove the tail.
  3. Treat an update to an existing key like an access: refresh its recency, then overwrite its value. Eviction should only trigger after an insertion makes the size exceed capacity — never on a get or on an in-place update.
  4. In Python, collections.OrderedDict does all of this for you: move_to_end(key) refreshes recency and popitem(last=False) removes the LRU entry. In Java, a LinkedHashMap with accessOrder=true plus an overridden removeEldestEntry is the equivalent shortcut.

Loading coding console...