Quick Overview

A coding problem that simulates a fixed-capacity least-recently-used cache over a sequence of get and put operations and returns the result of every get. It tests exact recency rules for reads, updates and evictions, and an implementation that handles each operation in constant average time.

Simulate a Least-Recently-Used Cache over Get and Put Operations

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A cache holds key-value pairs up to a fixed capacity. When it is full and a new key must be added, it evicts the key that was used least recently. Simulate such a cache over a sequence of `get` and `put` operations and return the result of every `get`. ### Function Signature ```python def simulate_lru_cache(capacity: int, operations: list[str], arguments: list[list[int]]) -> list[int]: ``` ### Rules - The cache starts empty and never holds more than `capacity` keys. - `operations[i]` is `"get"` or `"put"`, and `arguments[i]` holds that operation's arguments. - `"get"` with `[key]`: if `key` is in the cache, the result is its value and `key` becomes the most recently used key. Otherwise the result is `-1` and nothing changes. - `"put"` with `[key, value]`: if `key` is in the cache, replace its value and make it the most recently used key. Otherwise, if the cache already holds `capacity` keys, first evict the least recently used key, then insert `key` with `value` as the most recently used key. A `put` produces no result. - A key's recency is set by its latest successful `get` or its latest `put`. - Return one integer per `"get"`, in the order the operations appear. - The intended solution handles every operation in O(1) average time. ### Constraints - `1 <= capacity <= 3000` - `1 <= len(operations) == len(arguments) <= 2 * 10^5` - `arguments[i]` has length 1 when `operations[i]` is `"get"` and length 2 when it is `"put"`. - `0 <= key <= 10^4` - `0 <= value <= 10^9`, so a stored value is never `-1`, and every number fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: capacity = 2 operations = ["put", "put", "get", "put", "get", "get", "get"] arguments = [[5, 50], [7, 70], [5], [9, 90], [7], [5], [9]] Output: [50, -1, 50, 90] ``` Reading key `5` makes key `7` the least recently used key, so `put 9` evicts key `7`. **Example 2** ```text Input: capacity = 2 operations = ["put", "put", "put", "put", "get", "get", "get"] arguments = [[1, 10], [2, 20], [1, 15], [3, 30], [1], [2], [3]] Output: [15, -1, 30] ``` The third operation replaces key `1`'s value with `15` and makes it the most recently used key, so `put 3` evicts key `2`. **Example 3** ```text Input: capacity = 1 operations = ["get", "put", "get", "put", "get", "get"] arguments = [[4], [4, 0], [4], [6, 1], [4], [6]] Output: [-1, 0, -1, 1] ``` A stored value can be `0`. With capacity `1`, inserting key `6` evicts key `4`.

Overview: A coding problem that simulates a fixed-capacity least-recently-used cache over a sequence of get and put operations and returns the result of every get. It tests exact recency rules for reads, updates and evictions, and an implementation that handles each operation in constant average time.

A cache stores key-value pairs and can hold at most `capacity` keys. When it is full and a new key must be added, it evicts the key that was used least recently. Simulate such a cache over a sequence of `get` and `put` operations and return the result of every `get`. Implement `simulate_lru_cache(capacity, operations, arguments)`. `operations[i]` is `"get"` or `"put"`, and `arguments[i]` holds that operation's arguments. In JavaScript the third parameter is named `args` (the name `arguments` is reserved there); it has the same position and meaning. ### Rules - The cache starts empty and never holds more than `capacity` keys. - `"get"` with `[key]`: if `key` is in the cache, the result is its value and `key` becomes the most recently used key. Otherwise the result is `-1` and nothing changes. - `"put"` with `[key, value]`: if `key` is already in the cache, replace its value and make it the most recently used key. Otherwise, if the cache already holds `capacity` keys, first evict the least recently used key, then insert `key` with `value` as the most recently used key. A `put` produces no result. - A key's recency is set by its latest successful `get` or its latest `put`. - Return a list with one integer per `"get"`, in the order the operations appear. If there is no `get`, return an empty list. - Aim to handle every operation in O(1) average time. ### Constraints - `1 <= capacity <= 3000` - `1 <= len(operations) == len(arguments) <= 2 * 10^5` - `operations[i]` is exactly `"get"` or `"put"`. - `arguments[i]` has length 1 (`[key]`) when `operations[i]` is `"get"` and length 2 (`[key, value]`) when it is `"put"`. - `0 <= key <= 10^4` - `0 <= value <= 10^9`, so a stored value is never `-1`. - Every number fits in a 32-bit signed integer; no value exceeds 2^31 - 1. ### Example 1 ```text Input: capacity = 2 operations = ["put", "put", "get", "put", "get", "get", "get"] arguments = [[5, 50], [7, 70], [5], [9, 90], [7], [5], [9]] Output: [50, -1, 50, 90] ``` Reading key `5` makes key `7` the least recently used key, so `put 9` evicts key `7`. ### Example 2 ```text Input: capacity = 2 operations = ["put", "put", "put", "put", "get", "get", "get"] arguments = [[1, 10], [2, 20], [1, 15], [3, 30], [1], [2], [3]] Output: [15, -1, 30] ``` The third operation replaces key `1`'s value with `15` and makes it the most recently used key, so `put 3` evicts key `2`.

Constraints

  • 1 <= capacity <= 3000
  • 1 <= len(operations) == len(arguments) <= 2 * 10^5
  • operations[i] is exactly "get" or "put"
  • arguments[i] has length 1 ([key]) when operations[i] is "get" and length 2 ([key, value]) when it is "put"
  • 0 <= key <= 10^4
  • 0 <= value <= 10^9, so a stored value is never -1
  • Every number fits in a 32-bit signed integer; no value exceeds 2^31 - 1

Examples

Input: (2, ['put', 'put', 'get', 'put', 'get', 'get', 'get'], [[5, 50], [7, 70], [5], [9, 90], [7], [5], [9]])

Expected Output: [50, -1, 50, 90]

Explanation: Source example 1: reading key 5 makes key 7 least recently used, so put 9 evicts key 7.

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

Expected Output: [15, -1, 30]

Explanation: Source example 2: re-putting key 1 replaces its value and refreshes it, so put 3 evicts key 2.

Hints

  1. A get of a key that is not cached returns -1 and must leave both the stored keys and their recency order untouched.
  2. Eviction happens only when a put brings a key the cache does not already hold into a full cache; updating a cached key never evicts anything.
  3. A successful get and every put both make the key the most recently used one, so you need to find a key's value and the least recently used key without scanning the whole cache.

Loading coding console...

Show the approach

Approach

Keep, for every key, its current value and a flag saying whether it is cached, and keep the cached keys in a doubly linked list ordered from least recently used (right after a head sentinel) to most recently used (right before a tail sentinel). Because keys are integers in [0, 10^4], the list links live in two integer arrays indexed by key, with two extra slots for the sentinels, so every lookup, unlink and append is O(1) with no hashing.

Invariant: after each operation the list holds exactly the cached keys, never more than capacity of them, ordered by the time of each key's latest successful get or latest put, and value[key] is the latest value put for every cached key.

  • A get of a key that is not cached records -1 and touches nothing, matching the rule that nothing changes on a miss.
  • A get of a cached key moves it to the tail and records its value.
  • A put of a cached key moves it to the tail and overwrites its value; the number of cached keys does not change, so nothing is evicted even when the cache is full.
  • A put of a new key into a full cache first removes the key right after the head sentinel, which by the invariant is the least recently used key, then appends the new key at the tail.

Each step preserves the invariant, so every get returns exactly what the rules prescribe, and results are appended in operation order.

Edge cases: a get on an empty cache returns -1; a sequence with no get returns an empty list; with capacity 1 every new key evicts the only cached key; value 0 is a legitimate stored value and cannot be confused with the -1 miss marker because values are never negative.

Time complexity:
O(n + K), where n = len(operations) and K is the largest key (at most 10^4)
Space complexity:
O(n + K)