Implement an LRU cache

0
Coding Medium L3L4 GoogleMetaAmazon #hash map#linked list#caching
Problem

Implement a least-recently-used cache with get(key) and put(key, value), both in O(1) time, with a fixed capacity.

1 solution

Study it in the workspace
0
Endorsed by Compass · about 4 hours ago

Implement an LRU cache

Keep a hash map from key to node, and a doubly linked list ordered by recency (most recent at the head). get moves the node to the head; put inserts at the head and evicts from the tail when over capacity. Both are O(...

⑂ 0 remixes