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.

Solution

def solution(capacity, operations):
    class Node:
        __slots__ = ('key', 'value', 'prev', 'next')

        def __init__(self, key=None, value=None):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None

    def remove(node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def add_to_end(node):
        prev = tail.prev
        prev.next = node
        node.prev = prev
        node.next = tail
        tail.prev = node

    def move_to_end(node):
        remove(node)
        add_to_end(node)

    head = Node()
    tail = Node()
    head.next = tail
    tail.prev = head

    cache = {}
    results = []

    for op in operations:
        cmd = op[0]

        if cmd == 'put':
            key, value = op[1], op[2]
            if capacity == 0:
                results.append(None)
                continue

            if key in cache:
                node = cache[key]
                node.value = value
                move_to_end(node)
            else:
                if len(cache) == capacity:
                    lru = head.next
                    remove(lru)
                    del cache[lru.key]
                node = Node(key, value)
                cache[key] = node
                add_to_end(node)
            results.append(None)

        elif cmd == 'get':
            key = op[1]
            if key in cache:
                node = cache[key]
                move_to_end(node)
                results.append(node.value)
            else:
                results.append(-1)

        elif cmd == 'peek':
            key = op[1]
            if key in cache:
                results.append(cache[key].value)
            else:
                results.append(-1)

        elif cmd == 'delete':
            key = op[1]
            if key in cache:
                node = cache.pop(key)
                remove(node)
                results.append(True)
            else:
                results.append(False)

        else:
            raise ValueError('Unknown operation: {}'.format(cmd))

    return results

Time complexity: O(1) amortized per operation, or O(m) total for m operations. Space complexity: O(capacity).

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.