LRU Cache

medium

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

Implement the LRUCache class:

LRUCache(int capacity) initializes the cache with a positive size capacity.
int get(int key) returns the value of the key if it exists, otherwise -1.
void put(int key, int value) updates the value of the key if it exists. Otherwise adds the key-value pair. If inserting causes the count to exceed capacity, evict the least recently used key.

Both get and put must run in average O(1) time.

Test Cases

Copy an input into the main harness and Run to verify

Input

LRUCache(2), put(1,1), put(2,2), get(1), put(3,3), get(2), get(3)

Expected Output

1, -1, 3

Explanation: put(3,3) evicts key 2 because key 1 was used more recently, so get(2) returns -1.

Hint 1 — click to reveal

You need two things at once: O(1) lookup, and O(1) removal from the middle of an ordering.

Hint 2 — click to reveal

A hash map gives the first; a doubly linked list gives the second. Combine them.

Java Compiler