Build a Least-Recently-Used Store

Implement an in-memory key-value store with least-recently-used eviction.

The store is initialized with a positive integer capacity and supports two operations:

• get(key): Return the value associated with key if it exists; otherwise return -1. Accessing a key makes it the most recently used key.
• put(key, value): Insert or update key with value. Updating an existing key also makes it the most recently used key. If inserting a new key causes the number of keys to exceed capacity, evict the least recently used key.

For this interview variant, you do not need to use a linked list. An implementation based on a hash map plus a dynamic array/list is acceptable, even if moving keys in the list costs linear time.

Example:

store = Store(capacity = 2)
put(1, 10)
put(2, 20)
get(1)      -> 10   # key 1 becomes most recently used
put(3, 30)          # evicts key 2
get(2)      -> -1
get(3)      -> 30
put(1, 15)          # updates key 1 and makes it most recently used
get(1)      -> 15

Build a Least-Recently-Used Store

Implement a simulator for an in-memory key-value store with least-recently-used (LRU) eviction. The store starts empty and has a fixed positive integer capacity. You are given the commands as three parallel arrays: operations, keys, and values. For each index i:

• If operations[i] == "put", insert or update keys[i] with values[i].
• If operations[i] == "get", return the current value for keys[i], or -1 if the key does not exist. In this case values[i] should be ignored.

LRU rules:

• A successful get makes that key the most recently used.
• A put on either a new key or an existing key makes that key the most recently used.
• If inserting a new key would make the number of stored keys exceed capacity, evict the least recently used key first.

Return a list containing the outputs of all get operations in the order they occur.

For this interview variant, a hash map plus a list of key usage order is acceptable, even if moving keys in the list takes linear time.

Constraints

• 1 <= capacity <= 1000
• 0 <= len(operations) <= 2000
• len(operations) == len(keys) == len(values)
• operations[i] is either "get" or "put"
• -10^9 <= keys[i], values[i] <= 10^9

Hints

1. Use a hash map to store the current value for each key.
2. Keep a list of keys ordered from least recently used to most recently used. Whenever a key is accessed or updated, move it to the end.