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

Build a least-recently-used cache | Anthropic Coding Question

Build a least-recently-used cache

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Implement a fixed-capacity key-value cache with least-recently-used eviction. Requirements: - `get(key)` returns the value for `key`, or `-1` if the key does not exist. - `put(key, value)` inserts a new key or updates an existing key. - Any successful `get` or `put` operation makes that key the most recently used. - When the cache exceeds its capacity, evict the least recently used key. - Target average `O(1)` time per operation.

Quick Answer: This question evaluates a candidate's competence in designing and implementing efficient in-memory cache mechanisms, focusing on data structures, eviction policies, and algorithmic time-space complexity.

Implement an LRU (least-recently-used) cache simulator with a fixed capacity. You are given a cache capacity, a list of operations, and the arguments for each operation. A "get" operation should return the value for the key if it exists, or -1 otherwise. A "put" operation should insert or update a key-value pair. Any successful "get" and every "put" make that key the most recently used. If inserting a new key would exceed capacity, evict the least recently used key first. Return the result of every operation in order, using None for each "put" operation.

Constraints

1 <= capacity <= 10^5
0 <= len(operations) == len(arguments) <= 2 * 10^5
operations[i] is either "get" or "put"
For "get", arguments[i] has length 1; for "put", arguments[i] has length 2
-10^9 <= key, value <= 10^9
Target average time per operation: O(1)

Examples

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

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

Explanation: After inserting 1 and 2, get(1) makes key 1 most recently used. put(3,3) evicts key 2. Later put(4,4) evicts key 1.

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

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

Explanation: Updating an existing key should change its value and move it to most recently used. Key 1 is later evicted when key 4 is inserted.

Input: (1, ["put", "put", "get", "get", "put", "get"], [(1, 10), (2, 20), (1,), (2,), (2, 30), (2,)])

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

Explanation: With capacity 1, every new key evicts the previous one. Updating key 2 changes its stored value to 30.

Input: (2, ["get", "put", "put", "get", "put", "get", "get"], [(5,), (-1, -10), (5, 50), (-1,), (6, 60), (5,), (6,)])

Expected Output: [-1, None, None, -10, None, -1, 60]

Explanation: The first get misses. Accessing key -1 makes it most recently used, so inserting key 6 evicts key 5.

Input: (3, [], [])

Expected Output: []

Explanation: No operations means no outputs.

Hints

You need one structure for fast lookup by key and another for maintaining usage order.
A doubly linked list with dummy head and tail nodes lets you remove and reinsert nodes in O(1).

Quick Overview

This question evaluates a candidate's competence in designing and implementing efficient in-memory cache mechanisms, focusing on data structures, eviction policies, and algorithmic time-space complexity.