// LRU Cache — HARD

// Category: design

Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**.

Implement the `LRUCache` class:

- `LRUCache(capacity)` — initialize the LRU cache with a positive size `capacity`.

- `get(key)` — return the value of the `key` if it exists, otherwise return `-1`.

- `put(key, value)` — update the value of the `key` if it exists, or insert the key-value pair. If the number of keys exceeds `capacity`, evict the least recently used key.

Example: LRUCache(2): put(1,1), put(2,2), get(1)→1, put(3,3), get(2)→-1, put(4,4), get(1)→-1, get(3)→3, get(4)→4

Output: All operations as described