**LRU Cache** ===================================== **Problem Statement** ------------------- Design a data structure that supports the following two operations: - `insert(key, value)`: Inserts a `key-value` pair into the data structure. - `get(key)`: Returns the value associated with the given `key`. If the `key` is not found, returns `-1`. The data structure should maintain a Least Recently Used (LRU) cache. When the cache reaches its capacity, the oldest item should be removed first. **Rules and Constraints** ------------------------- * The `insert` operation takes `key` and `value` as input, and returns `null`. * The `get` operation takes `key` as input and returns the associated `value` if found, or `-1` otherwise. * The cache has a fixed capacity `capacity`. * The data structure should use the most efficient time and space complexity. * The `insert` operation should update the LRU order of the keys in the cache. * The `get` operation should return the value associated with the given `key` if it exists in the cache, without modifying the LRU order. * If the cache is empty or does not contain the given `key`, `get` should return `-1`. **Assumptions** --------------- * The `key` and `value` are integers. * The `capacity` is a positive integer. * The input data is valid (i.e., the number of operations will not exceed the capacity). **Metrics for Success** ----------------------- * The data structure should implement the `insert` and `get` operations efficiently (i.e., with low time complexity). * The data structure should maintain the LRU order of the keys in the cache. * The data structure should use a reasonable amount of space (i.e., linear or sublinear with respect to the input data). ### Example **Input:** {"capacity":2,"ops":["put","put","get"]} **Output:** [null,null,1]