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 Machine Learning Engineer candidates at Anthropic during technical interviews.

Implement an LRU cache | Anthropic Coding Question

Quick Overview

This question evaluates competency in designing efficient key-value caching mechanisms, enforcing capacity constraints and eviction policies while maintaining O(1) average-time operations, testing algorithmic efficiency and stateful data-structure design.

Implement an LRU cache

Company: Anthropic

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a fixed-capacity key-value cache with least-recently-used eviction. Support the following operations: - `get(key) -> value`: return the value associated with `key` if it exists; otherwise return `-1` - `put(key, value)`: insert or update the key; if the cache exceeds its capacity, evict the least recently used key Both operations must run in O(1) average time. You may assume: - `capacity` is a positive integer - keys and values are integers

Quick Answer: This question evaluates competency in designing efficient key-value caching mechanisms, enforcing capacity constraints and eviction policies while maintaining O(1) average-time operations, testing algorithmic efficiency and stateful data-structure design.

Design a fixed-capacity key-value cache that evicts the least recently used entry when it becomes full. Process a sequence of cache operations and return the results of all 'get' operations in order. The cache supports: - get(key): return the value for key if it exists, otherwise return -1 - put(key, value): insert or update the key with the given value A key becomes most recently used whenever it is successfully read with 'get', inserted with 'put', or updated with 'put'. Both operations must run in O(1) average time.

Constraints

1 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Each operation is either ('get', key) or ('put', key, value)
-10^9 <= key, value <= 10^9
Your design should achieve O(1) average time for each operation

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: [1, -1, -1, 3, 4]

Explanation: After accessing key 1, key 2 becomes least recently used and is evicted by put(3, 3). Later key 1 is evicted by put(4, 4).

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

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

Explanation: Updating key 1 also makes it most recently used, so when key 3 is inserted, key 2 is evicted.

Input: (1, [('put', 1, 100), ('get', 1), ('put', 2, 200), ('get', 1), ('get', 2), ('put', 2, 250), ('get', 2)])

Expected Output: [100, -1, 200, 250]

Explanation: With capacity 1, inserting key 2 evicts key 1. Updating key 2 changes its stored value to 250.

Input: (3, [])

Expected Output: []

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

Hints

A hash map can tell you whether a key exists and where its node is in O(1) average time.
Use a doubly linked list to maintain usage order so you can move a key to the front and evict the least recently used key from the back in O(1).

Quick Overview