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.

Implement a Least-Recently-Used Cache | Anthropic Coding Question

Implement a Least-Recently-Used Cache

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design and implement an in-memory least-recently-used cache. Requirements: - The cache is initialized with a positive integer capacity. - Implement `get(key)`: return the value associated with `key` if it exists; otherwise return `-1` or `null`. - Implement `put(key, value)`: insert or update the value for `key`. - Any successful `get` or `put` makes that key the most recently used item. - If inserting a new key causes the cache to exceed capacity, evict the least recently used key. - Both `get` and `put` should run in O(1) average time. Explain your data structures, edge cases, and time/space complexity.

Quick Answer: This question evaluates a candidate's ability to design and implement an efficient in-memory cache with eviction behavior, testing understanding of data structure selection, state management, and time/space complexity under capacity constraints.

Design and implement an in-memory Least-Recently-Used (LRU) cache. Because this platform expects a function instead of a class, implement `solution(capacity, operations)`. - `capacity` is the maximum number of keys the cache can hold. - Each operation is a list of 3 integers: - `[1, key, 0]` means `get(key)` - `[2, key, value]` means `put(key, value)` - For every `get`, append the returned value to the answer list. - If a key does not exist, `get` should return `-1`. - Any successful `get` or any `put` makes that key the most recently used. - If inserting a new key would exceed capacity, evict the least recently used key. To achieve O(1) average time per operation, a correct solution should combine: - a hash map from key to node, and - a doubly linked list that stores keys from most recently used to least recently used. Important edge cases to handle: - empty `operations` - capacity of 1 - updating an existing key should not increase cache size - missing keys on `get` - negative keys or values

Constraints

1 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Each operation has exactly 3 integers
operation[0] is either 1 (get) or 2 (put)
-10^9 <= key, value <= 10^9

Examples

Input: (2, [[2, 1, 1], [2, 2, 2], [1, 1, 0], [2, 3, 3], [1, 2, 0], [2, 4, 4], [1, 1, 0], [1, 3, 0], [1, 4, 0]])

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

Explanation: After `get(1)`, key 1 becomes most recent, so key 2 is evicted when key 3 is inserted. Later key 1 is evicted when key 4 is inserted.

Input: (1, [[2, 2, 1], [1, 2, 0], [2, 3, 2], [1, 2, 0], [1, 3, 0]])

Expected Output: [1, -1, 2]

Explanation: With capacity 1, inserting key 3 evicts key 2.

Input: (2, [[2, 2, 1], [2, 2, 2], [1, 2, 0], [2, 1, 1], [2, 4, 1], [1, 2, 0], [1, 1, 0], [1, 4, 0]])

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

Explanation: Updating key 2 changes its value to 2 and does not increase cache size. After inserting key 1, key 2 becomes least recent, so inserting key 4 evicts key 2.

Input: (3, [])

Expected Output: []

Explanation: No operations means there are no `get` results to return.

Input: (2, [[2, -1, -10], [2, -2, -20], [1, -1, 0], [2, -3, -30], [1, -2, 0], [1, -1, 0], [1, -3, 0]])

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

Explanation: Negative keys and values are valid. Accessing key -1 makes it most recent, so key -2 is evicted when key -3 is inserted.

Hints

A hash map can find a key in O(1), but by itself it cannot tell you which key is least recently used.
Use a doubly linked list with dummy head and tail nodes so you can remove or move any cache entry in O(1).

Quick Overview

This question evaluates a candidate's ability to design and implement an efficient in-memory cache with eviction behavior, testing understanding of data structure selection, state management, and time/space complexity under capacity constraints.