# Implement a Constant-Time LRU Cache Implement a fixed-capacity least-recently-used cache. The captured source identifies an LRU cache coding problem but does not provide an exact interface. The operation driver below is a deterministic PracHub practice wrapper; its function and command names were not supplied verbatim by the source. The required console entry point is: ```python def run_lru_cache(capacity: int, operations: list[list[object]]) -> list[object]: ... ``` Create one initially empty cache and process `operations` from left to right. Append exactly one result for every operation: - `["put", key, value]` inserts or updates the entry, marks `key` as most recently used, and appends `None`. - `["get", key]` on a present key marks it as most recently used and appends `["HIT", value]`. - `["get", key]` on an absent key appends `["MISS"]` and does not change the recency order. - Any unknown or malformed operation appends `["ERROR"]`, changes neither the cache contents nor recency order, and processing continues. An operation is malformed if it is not a list, has the wrong arity, or contains an invalid key or value. When a valid `put` inserts a new key while the cache is at capacity, evict the least recently used key before inserting. Updating an existing key must not evict any other key. Keys must be either strings or non-Boolean signed 64-bit integers. Values must be JSON scalar values: `None`, a Boolean, a signed 64-bit integer, a finite float, or a string. In particular, `NaN` and positive or negative infinity are invalid values. The tagged `HIT` and `MISS` results distinguish a stored `None` from a missing key. `capacity` must be a non-Boolean positive integer no greater than `200_000`, and the outer `operations` argument must be a list. If either top-level argument is invalid, raise `ValueError` before processing any operation. An empty operation list returns `[]`. Example: ```python run_lru_cache(2, [ ["put", "a", None], ["put", "b", 2], ["get", "a"], ["put", "c", 3], ["get", "b"], ["get", "a"], ["unknown"], ]) # [None, None, ["HIT", None], None, ["MISS"], ["HIT", None], ["ERROR"]] ``` ## Constraints and Clarifications - `0 <= len(operations) <= 200_000`. - Both valid `get` and `put` operations should run in `O(1)` expected time. - Repeated `put` operations for the same key update its value and recency. - All operations are sequential, so each successful access determines the recency order for the next operation. - Explain how the design maintains lookup and recency invariants after every valid operation. ## Hints - One structure can provide constant-time lookup while another maintains a removable ordering. - Test capacity one, repeated updates, misses, stored `None`, malformed operations, and alternating accesses before an eviction.