LRU Cache Implementation

Implement a LRU Cache. The cache should support the following operations: get and put. Get function should return the value of the key if the key exists in the cache, or -1 if it does not exist. Put function should insert the key-value if the key is not present. If the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. Assumed maximum call count is 10^5, and cache capacity is at least 1. No duplicate keys will be passed. 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