LRU Cache Implementation

Design and implement an LRU (Least Recently Used) Cache. It should support get(key) and put(key, value) operations. When the cache reaches its maximum capacity, it should remove the least recently used item before inserting a new item. Example Input put(1, 1)