Quick Overview

This question evaluates a candidate's ability to design and implement an efficient in-memory cache with eviction behavior, testing understanding of data structure selection, state management, and time/space complexity under capacity constraints.

Implement a Least-Recently-Used Cache

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design and implement an in-memory least-recently-used cache. Requirements: - The cache is initialized with a positive integer capacity. - Implement `get(key)`: return the value associated with `key` if it exists; otherwise return `-1` or `null`. - Implement `put(key, value)`: insert or update the value for `key`. - Any successful `get` or `put` makes that key the most recently used item. - If inserting a new key causes the cache to exceed capacity, evict the least recently used key. - Both `get` and `put` should run in O(1) average time. Explain your data structures, edge cases, and time/space complexity.

Quick Answer: This question evaluates a candidate's ability to design and implement an efficient in-memory cache with eviction behavior, testing understanding of data structure selection, state management, and time/space complexity under capacity constraints.

Design and implement an in-memory Least-Recently-Used (LRU) cache. Because this platform expects a function instead of a class, implement `solution(capacity, operations)`. - `capacity` is the maximum number of keys the cache can hold. - Each operation is a list of 3 integers: - `[1, key, 0]` means `get(key)` - `[2, key, value]` means `put(key, value)` - For every `get`, append the returned value to the answer list. - If a key does not exist, `get` should return `-1`. - Any successful `get` or any `put` makes that key the most recently used. - If inserting a new key would exceed capacity, evict the least recently used key. To achieve O(1) average time per operation, a correct solution should combine: - a hash map from key to node, and - a doubly linked list that stores keys from most recently used to least recently used. Important edge cases to handle: - empty `operations` - capacity of 1 - updating an existing key should not increase cache size - missing keys on `get` - negative keys or values

Constraints

  • 1 <= capacity <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • Each operation has exactly 3 integers
  • operation[0] is either 1 (get) or 2 (put)
  • -10^9 <= key, value <= 10^9

Examples

Input: (2, [[2, 1, 1], [2, 2, 2], [1, 1, 0], [2, 3, 3], [1, 2, 0], [2, 4, 4], [1, 1, 0], [1, 3, 0], [1, 4, 0]])

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

Explanation: After `get(1)`, key 1 becomes most recent, so key 2 is evicted when key 3 is inserted. Later key 1 is evicted when key 4 is inserted.

Input: (1, [[2, 2, 1], [1, 2, 0], [2, 3, 2], [1, 2, 0], [1, 3, 0]])

Expected Output: [1, -1, 2]

Explanation: With capacity 1, inserting key 3 evicts key 2.

Hints

  1. A hash map can find a key in O(1), but by itself it cannot tell you which key is least recently used.
  2. Use a doubly linked list with dummy head and tail nodes so you can remove or move any cache entry in O(1).

Loading coding console...