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

What role is this question designed for?

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

LRU Cache | Anthropic Coding Question

Quick Overview

This question evaluates a candidate's ability to design a data structure combining a hash map with a doubly linked list to achieve constant-time access and updates. It tests practical application of algorithmic design under strict complexity constraints, commonly used in coding interviews to assess handling of edge cases like eviction order and pointer maintenance.

LRU Cache

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# LRU Cache Implement a fixed-capacity cache with **Least-Recently-Used** eviction. When the cache is full and a new key is inserted, the key that was accessed least recently is evicted. Both reads and writes count as accesses, and both must run in `O(1)` average time. The cache is exercised by a list of operations. Your function receives an integer `capacity` and `ops: List[List[str]]`, and returns `List[str]` containing the result of each `GET`, in order (`PUT` produces no output). - `["GET", key]` — return the value associated with `key` as a string, or `"-1"` if the key is not present. A successful `GET` marks the key as most-recently used. - `["PUT", key, value]` — insert or update `key = value`, marking it most-recently used. If inserting a new key exceeds `capacity`, first evict the least-recently-used key. Keys and values are integers represented as strings. ## Constraints - `1 <= capacity <= 10^5`. - `1 <= len(ops) <= 2 * 10^5`. - Every `GET` and `PUT` must be `O(1)` average time (use a hash map plus a doubly linked list, or an equivalent structure). - Pay careful attention to boundary conditions: updating an existing key must not grow the size or evict anything; evicting must correctly fix both the head and the tail of the recency list; a `capacity` of 1 must still work. ## Example Input: ``` capacity = 2 ops = [ ["PUT", "1", "10"], ["PUT", "2", "20"], ["GET", "1"], ["PUT", "3", "30"], ["GET", "2"], ["GET", "3"] ] ``` Output: ``` ["10", "-1", "30"] ``` Explanation: after `GET 1`, key 1 is most-recently used, so inserting key 3 (which exceeds capacity 2) evicts key 2. `GET 2` then misses (`-1`), while keys 1 and 3 remain.

Quick Answer: This question evaluates a candidate's ability to design a data structure combining a hash map with a doubly linked list to achieve constant-time access and updates. It tests practical application of algorithmic design under strict complexity constraints, commonly used in coding interviews to assess handling of edge cases like eviction order and pointer maintenance.

Implement a fixed-capacity cache with **Least-Recently-Used** eviction. When the cache is full and a new key is inserted, the key that was accessed least recently is evicted. Both reads and writes count as accesses, and both must run in `O(1)` average time. Your function receives an integer `capacity` and `ops: List[List[str]]`, and returns `List[str]` containing the result of each `GET`, in order (`PUT` produces no output). - `["GET", key]` — return the value associated with `key` as a string, or `"-1"` if the key is not present. A successful `GET` marks the key as most-recently used. - `["PUT", key, value]` — insert or update `key = value`, marking it most-recently used. If inserting a new key exceeds `capacity`, first evict the least-recently-used key. Keys and values are integers represented as strings. **Constraints** - `1 <= capacity <= 10^5`. - `1 <= len(ops) <= 2 * 10^5`. - Every `GET` and `PUT` must be `O(1)` average time (hash map + doubly linked list). - Boundary care: updating an existing key must not grow the size or evict; evicting must fix both head and tail of the recency list; `capacity = 1` must work.

Constraints

1 <= capacity <= 10^5
1 <= len(ops) <= 2 * 10^5
Each op is ["GET", key] or ["PUT", key, value]; keys and values are integers represented as strings.
Every GET and PUT must run in O(1) average time.
Updating an existing key must not grow the size or evict; capacity = 1 must still work.

Examples

Input: (2, [["PUT", "1", "10"], ["PUT", "2", "20"], ["GET", "1"], ["PUT", "3", "30"], ["GET", "2"], ["GET", "3"]])

Expected Output: ["10", "-1", "30"]

Explanation: GET 1 marks key 1 most-recently used, so inserting key 3 (over capacity 2) evicts key 2. GET 2 misses; keys 1 and 3 remain.

Input: (1, [["PUT", "1", "1"], ["PUT", "2", "2"], ["GET", "1"], ["GET", "2"]])

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

Explanation: Capacity 1: PUT 2 evicts key 1, so GET 1 misses and GET 2 returns 2.

Input: (2, [["PUT", "1", "1"], ["PUT", "2", "2"], ["PUT", "1", "10"], ["PUT", "3", "3"], ["GET", "1"], ["GET", "2"], ["GET", "3"]])

Expected Output: ["10", "-1", "3"]

Explanation: Updating existing key 1 does not grow size but marks it MRU, so PUT 3 evicts key 2 (the LRU). Key 1 now holds the updated value 10.

Input: (2, [["PUT", "1", "1"], ["PUT", "2", "2"], ["GET", "1"], ["PUT", "3", "3"], ["GET", "2"]])

Expected Output: ["1", "-1"]

Explanation: GET 1 refreshes key 1's recency, so PUT 3 evicts key 2; GET 2 then misses.

Input: (1, [["GET", "5"]])

Expected Output: ["-1"]

Explanation: GET on an empty cache misses and returns -1.

Input: (2, [["PUT", "1", "100"], ["GET", "1"], ["PUT", "1", "200"], ["GET", "1"]])

Expected Output: ["100", "200"]

Explanation: Repeated updates of the same key return the latest stored value without eviction.

Hints

Combine a hash map (key -> node) for O(1) lookup with a doubly linked list that orders nodes by recency.
Use sentinel head/tail nodes so insert-at-front and remove never hit a null-pointer edge case, even at capacity 1.
On both GET (hit) and PUT (existing key), unlink the node and re-insert it at the front to mark it most-recently used; only insert a brand-new key triggers an eviction of tail.prev.