dsa · medium

LRU Cache

GreyOrangeHash MapLinked ListDesign

Implement an LRU cache of integer keys and values with fixed capacity.

Methods

• get(key) → the value, or -1 if missing. A hit counts as a use.
• put(key, value) insert or overwrite. If the cache would exceed capacity, evict the least recently used key first.

Both operations should be O(1). GreyOrange tagged LLD.

Fill in the LRUCache class. The starter already walks ops / args and calls your methods — leave the driver at the bottom as-is. Constructors contribute null; booleans print as true / false.

**Example**

`` LRUCache(2) → null put(1, 1) → null put(2, 2) → null get(1) → 1 put(3, 3) → null get(2) → -1 put(4, 4) → null get(1) → -1 get(3) → 3 get(4) → 4 ``

Constraints

Capacity >= 1, calls <= 3000

Examples

Example 1

Input:
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

Expected:
[null,null,null,1,null,-1,null,-1,3,4]

Open in the Dojo editor