LRU Cache

Medium

Design an LRU (Least Recently Used) cache with get(key) and put(key, value), both O(1). The constructor takes a positive capacity. get returns the value or -1; put inserts/updates and evicts the least recently used key when over capacity.

Example 1

Input:  operations = ["LRUCache","put","put","get","put","get","put","get","get","get"], values = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,null,-1,3,4]

Constraints

• 1 <= capacity <= 3000
• 0 <= key, value <= 10^4
• At most 2*10^5 calls.