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 Technical Screen 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 recency-eviction bounded cache

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory key–value store with a fixed capacity N that uses recency-based eviction. Support: get(key) -> value or -1 if missing, and put(key, value) which inserts or updates the key. When capacity is exceeded, evict the least-recently-accessed entry. Target amortized O( 1) time per operation and O(N) space. Describe the data structures you would use, provide pseudocode for both operations, and explain how you would handle: updates to existing keys, N = 0, thread-safety considerations, and how to extend the design to support peek (read without affecting recency) and delete(key).

Quick Answer: This question evaluates understanding of recency-based eviction (LRU) cache design and proficiency with core data structures and algorithmic complexity, including achieving amortized O(1) operations and O(N) space.

Design and implement a fixed-capacity in-memory key-value cache with recency-based eviction (an LRU cache). You are given a cache capacity and a sequence of operations. Each operation is one of: ('put', key, value) to insert or update a key and mark it as most recent, ('get', key) to return the value or -1 if missing and mark it as most recent if found, ('peek', key) to return the value or -1 without changing recency, and ('delete', key) to remove the key and return True if it existed or False otherwise. If inserting a new key would exceed capacity, evict the least recently used key. If capacity is 0, the cache should never store anything. Return a list containing the result of every operation in order; use None for 'put'. Single-threaded code is sufficient for this task, but in an interview follow-up you should be ready to explain why a hash map plus a doubly linked list achieves O(1) amortized time per operation, how updates to existing keys are handled, how N = 0 behaves, and what you would do for thread safety.

Constraints

0 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Keys and values are integers in the range [-10^9, 10^9]
Your solution should target O(1) amortized time per operation and O(capacity) extra space

Examples

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

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

Explanation: After get(1), key 1 becomes most recent, so inserting key 3 evicts key 2.

Input: (2, [('put', 1, 1), ('put', 2, 2), ('peek', 1), ('put', 3, 3), ('get', 1), ('delete', 2), ('delete', 4), ('peek', 3)])

Expected Output: [None, None, 1, None, -1, True, False, 3]

Explanation: peek(1) does not change recency, so key 1 is still the least recent and is evicted when key 3 is inserted. delete(2) succeeds, delete(4) does not.

Input: (2, [('put', 1, 5), ('put', 2, 6), ('put', 1, 7), ('put', 3, 8), ('get', 1), ('get', 2), ('get', 3)])

Expected Output: [None, None, None, None, 7, -1, 8]

Explanation: Updating key 1 changes its value to 7 and makes it most recent, so key 2 is evicted when key 3 is inserted.

Input: (0, [('put', 1, 1), ('get', 1), ('peek', 1), ('delete', 1)])

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

Explanation: With capacity 0, puts have no effect and the cache always behaves as empty.

Hints

A hash map gives O(1) lookup by key, but you also need O(1) removal when a key becomes most recent or is deleted.
Track recency with a doubly linked list from least recent to most recent. 'get' and updating an existing key should move that node to the most-recent end, while 'peek' should leave it in place.

Quick Overview

This question evaluates understanding of recency-based eviction (LRU) cache design and proficiency with core data structures and algorithmic complexity, including achieving amortized O(1) operations and O(N) space.