Implement an LRU cache — interview question

Implement a least-recently-used (LRU) cache with a fixed capacity and process a list of operations.

get k prints the value stored for key k, or -1 if it is not in the cache. A successful get makes k the most recently used key.
put k v stores value v for key k (replacing any old value) and makes k the most recently used key. If the cache then holds more than capacity keys, remove the least recently used one.

Both operations should run in O(1) average time.

Constraints

1 ≤ capacity ≤ 10^4
1 ≤ number of operations ≤ 10^5, at least one of them a get
Keys and values are integers between 0 and 10^9

Input and output

Input: Line 1: capacity and the number of operations q Next q lines: an operation
Output: One line per get: the value or -1.

Examples

Input 1

2 7
put 1 10
put 2 20
get 1
put 3 30
get 2
get 3
get 1

Output

get 1 makes key 1 recent, so put 3 evicts key 2.

Input 2

1 4
put 5 50
put 5 55
get 5
get 6

Output

55
-1

Updating a key replaces its value; a missing key gives -1.

Show hints

A JavaScript Map remembers insertion order, and its first key is the oldest.
To mark a key as recent, delete it and set it again.

Show the explanation

In JavaScript a Map iterates keys in insertion order, so it can serve as both the hash table and the recency list:

get: if the key exists, read the value, delete the key and set it again (moving it to the end, the "newest" position).
put: delete the key if present, set it, and if size > capacity, remove map.keys().next().value, the oldest key.

All of these are O(1) on average. In languages without an ordered map, the classic design is a hash map plus a doubly linked list: the map finds the node in O(1), and the list moves or removes nodes in O(1). Python's OrderedDict.move_to_end and popitem(last=False) provide the same structure.

LRU caches appear in browser caches, CDN edges, database buffer pools, and memoisation helpers.

Original UniCircle question. Last reviewed 22 Oct 2026.