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

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.

hard
Anthropic
Coding & Algorithms
Software Engineer

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]

Loading coding console...

Quick Overview

Build a least-recently-used cache

Constraints

Examples

Hints