Implement LRU Cache

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.