Implement an LRU cache supporting get(key) and put(key, value). When capacity is exceeded, evict the least recently used key while keeping average O(1) time per operation.
capacity = 2, operations = ["put", "put", "get", "put", "get", "get"]Output[null, null, 10, null, -1, 30]WhyKey 2 is evicted after key 1 is accessed and key 3 is inserted.capacity = 1, operations = ["put", "get", "put", "get", "get"]Output[null, 50, null, -1, 60]WhyOnly one key can remain in the cache at a time.`1 <= capacity <= 3000``0 <= key, value <= 10^9`At most `2 * 10^5` operationsAverage `O(1)` `get` and `put`