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.

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

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.

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.

Hints

  1. 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.
  2. 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.

Community answers

Answer by mpbaranowski

Pretty much the same as the provided solution, but in a OO style: def solution(capacity, operations): lru = LRU(capacity) collect = [] for op in operations: if op[0] == 'put': collect.append(lru.put(op[1], op[2])) elif op[0] == 'get': collect.append(lru.get(op[1])) elif op[0] == 'peek': collect.append(lru.peek(op[1])) elif op[0] == 'delete': collect.append(lru.delete(op[1])) return collect class DLLNode(): def init(self, key, val): self.prev = None self.nxt = None self.key = key self.val = val def extract(self): if self.prev: self.prev.nxt = self.nxt if self.nxt: self.nxt.prev = self.prev self.nxt = None self.prev = None class LRU(): def init(self, limit): self.head = DLLNode(-1,-1) self.tail = DLLNode(-1,-1) self.head.nxt = self.tail self.tail.prev = self.head self.cache = {} self.limit = limit self.count = 0 def put(self, key, val): node = None if key in self.cache: node = self.cache.get(key) node.val = val else: node = DLLNode(key, val) self.cache[key] = node self.count += 1 self._touched(key) if self.count > self.limit: evicted = self.tail.prev evicted.extract() self.cache.pop(evicted.key) self.count -= 1 return None def get(self, key): if key in self.cache: node = self.cache[key] self._touched(key) return node.val else: return -1 def peek(self, key): if key in self.cache: node = self.cache[key] return node.val else: return -1 def delete(self, key): if key in self.cache: node = self.cache[key] self.cache.pop(key) node.extract() return True else: return False def _touched(

Loading coding console...