Meta asks this design problem in nearly every onsite loop to test your data structure design skills.
Design a data structure that follows Least Recently Used (LRU) eviction. Implement LRUCache(capacity), get(key), and put(key, value). Both get and put must run in average time.
When put is called and the cache is at capacity, evict the least recently used key before inserting the new one. Any get or put on a key makes it the most recently used.
Constraints: , . Up to calls.