LRU Cache

Design and implement a data structure for LRU (Least Recently Used) cache. It should support the following operations: get and put. Get data get(key) - Retrieve the value (always positive) of the key if the key exists in the cache, otherwise return -1. Put data put(key, value) - Write the value to the cache. If the number of keys exceeds the cache capacity, it should invalidate the least recently used entry before writing a new value. Test Cases: LRUCache cache = new LRUCache( 2 ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 cache.get(3); // returns 3 cache.get(4); // returns 4 Constraints: The size can be up to 3000. 0 <= key, value <= 1,000,000. Example Input 2 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4