LRU

Implement Least Recently Used (LRU) cache.

You need to implement the following for the LRUCache class:

• LRUCache(int capacity) initializes the cache to store data of size: capacity.
• int get(int key) returns the value of the key if it exists, otherwise returns -1.
• void add(int key, int value) updates the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Note: Try to achieve each operation in O(1) time complexity.