Problem

Design a data structure that implements an LRU (Least Recently Used) cache. The cache should support the following operations:

• get(key): Retrieve the value of the key if the key exists in the cache, otherwise return -1.
• put(key, value): Update the value of the key if the key exists. If the key does not exist, add the key-value pair to the cache. If the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Examples

Example 1:

Input: cache = 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 (not found)
cache.put(4, 4)    # evicts key 1
cache.get(1)       # returns -1 (not found)
cache.get(3)       # returns 3
cache.get(4)       # returns 4

Constraints

• The capacity of the cache is between 1 and 3000.
• The key and value are both integers.