LRU Cache — JavaScript Coding Problem
Difficulty: hard | Category: design
Problem Description
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. `get` and `put` must each run in `O(1)` average time complexity.
Examples
Example 1
Input: 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