Fix the LRU cache replay of puts and gets

Review the AI's codeEasy12 min

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 after get:. 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 between put: 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 capacity is 0 or less. Otherwise, if the cache already holds capacity keys, 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
Inputlru_get_results(2, ["put:a:1", "put:b:2", "put:c:3", "get:a", "get:b", "get:c"])
Output[-1, 2, 3]
Example 2
Inputlru_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
Inputlru_get_results(2, ["put:a:1", "put:a:9", "get:a"])
Output[9]