LRU Cache

Design and implement a data structure for a Least Recently Used (LRU) cache that supports two operations in O(1) average time:

1. get(key) – Return the value of the key if it exists in the cache; otherwise return -1. Accessing the key makes it the most recently used.

2. put(key, value) – Update the value if the key exists; otherwise insert the key-value pair. If inserting causes the number of keys to exceed the cache’s fixed positive capacity, evict the least recently used key before the insertion.

Internally you must track the order of use so that the least recently used item can be identified and removed in constant time.