Fix the LRU cache replay of puts and gets
Your task
You asked an agent to test an LRU cache: a cache that, when full, drops the key used least recently. Its tests read the cache's private fields, so the team rewrote them to check only what a caller can see, the result of each get.
An assistant wrote lru_get_results(capacity, ops). It is in the editor. It has a bug. Find it and fix it.
Input and output:
capacity: the most keys the cache can hold. An integer, and it can be 0 or negative.ops: the operations, in order. Each is"put:<key>:<value>"or"get:<key>".- Return a list of integers, one for each get, in order: the value it found, or -1 for a miss.
Rules the tests check:
- The cache starts empty. Every key has a recency: a get that finds the key, or a put on it, makes it the most recently used.
"get:<key>": the key is everything afterget:. It can be empty and can contain:. If the key is in the cache, return its value and make it the most recently used. Otherwise return -1."put:<key>:<value>": the key is the text betweenput:and the next:, and it can be empty. The value is the rest. It must be 1 to 9 digits (0 to 9 only), and leading zeros are fine, so"007"means 7. 0 is a valid value.- Skip a put with no second
:, or with a value that is not 1 to 9 digits, such as"-1","x"or"". It changes nothing. - A put on a key already in the cache replaces its value and makes it the most recently used. The cache does not grow.
- A put on a new key stores nothing when
capacityis 0 or less. Otherwise, if the cache already holdscapacitykeys, first remove the least recently used key. Then store the new key as the most recently used. - Keys and op names are case sensitive. Any other line, such as
"noise"or"GET:a", is skipped. Only a get adds to the output. - No operations returns an empty list.
Examples
lru_get_results(capacity: int, ops: list[str]) -> list[int]Example 1
Input
lru_get_results(2, ["put:a:1", "put:b:2", "put:c:3", "get:a", "get:b", "get:c"])Output
[-1, 2, 3]Example 2
Input
lru_get_results(2, ["put:a:1", "put:b:2", "get:a", "put:c:3", "get:b", "get:a", "get:c"])Output
[1, -1, 1, 3]Example 3
Input
lru_get_results(2, ["put:a:1", "put:a:9", "get:a"])Output
[9]