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