How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Implement LRU cache with O(1) ops | Amazon Coding Question

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.

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

Expected Output: [-1]

Explanation: Reading from an empty cache returns -1 — the missing-key contract, with no puts performed first.

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

Expected Output: [None, None, None, 5, 2]

Explanation: Updating an existing key: put(1,0), put(2,2), then put(1,5) overwrites key 1's value to 5 and refreshes its recency without changing the size. No eviction occurs (still 2 entries), so get(1)=5 and get(2)=2.

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

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

Explanation: Capacity 3. After filling with 1,2,3, get(1) makes 1 most recent (LRU is now 2). put(4,4) overflows and evicts the LRU key 2, so get(2)=-1, while get(1)=1, get(3)=3, get(4)=4 all survive.

Input: (2, [['put', -1, -10], ['get', -1], ['put', -2, -20], ['put', -3, -30], ['get', -1], ['get', -2], ['get', -3]])

Expected Output: [None, -10, None, None, -1, -20, -30]

Explanation: Negative keys and values. get(-1)=-10 confirms -10 is a real stored value, distinct from the -1 missing-key sentinel. After put(-3,-30) overflows and evicts the LRU key -1, get(-1)=-1 (missing), get(-2)=-20, get(-3)=-30.

Hints

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.
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.
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.
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.

Quick Overview