Process LRU Cache Operations

Implement process_lru(capacity, operations) for a least recently used cache with integer keys and values.

Each operation is one of the following strings:

• "PUT key value": insert or update key. A successful update makes the key most recently used. If insertion makes the cache exceed capacity, evict the least recently used key.
• "GET key": append the stored value to the result, or append -1 if the key is absent. A successful lookup makes the key most recently used; a miss does not change recency.

Return the list of results from GET operations in their original order. This operation grammar is a pedagogical assumption that makes the named cache-design exercise deterministic.

Function Contract

process_lru(capacity: int, operations: list[str]) -> list[int]

Constraints

• 1 <= capacity <= 100000
• 0 <= len(operations) <= 200000
• Keys and values are integers in the inclusive range [-10^9, 10^9].
• Every operation follows one of the two formats above.

Examples

Example 1

Input:
capacity = 2
operations = ["PUT 1 10", "PUT 2 20", "GET 1", "PUT 3 30", "GET 2", "GET 3"]

Output: [10, -1, 30]

The lookup of key 1 makes key 2 least recently used, so inserting key 3 evicts key 2.

Example 2

Input:
capacity = 1
operations = ["PUT 7 4", "PUT 7 9", "GET 7", "PUT 8 5", "GET 7", "GET 8"]

Output: [9, -1, 5]

Updating key 7 replaces its value without creating a second entry. Inserting key 8 later evicts it.