Description
Build a positive-capacity cache with get and put. A successful get or any put makes a key most recently used. Evict the least recently used key when an insertion exceeds capacity; missing gets return -1.
Solution
from collections import OrderedDict
def create_lru_cache(capacity):
return {"capacity": capacity, "items": OrderedDict()}
def get(state, key):
items = state["items"]
if key not in items:
return -1
items.move_to_end(key)
return items[key]
def put(state, key, value):
items = state["items"]
items[key] = value
items.move_to_end(key)
if len(items) > state["capacity"]:
items.popitem(last=False)Examples
Example 1
- Input
[["LRUCache",2],["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]]- Output
[null,null,null,1,null,-1]
Reading 1 makes 2 the eviction candidate.
Example 2
- Input
[["LRUCache",1],["put",1,1],["put",1,8],["get",1]]- Output
[null,null,null,8]
An update replaces the value.
Example 3
- Input
[["LRUCache",1],["get",5]]- Output
[null,-1]
An empty cache misses.
Approach
Use a map plus a doubly linked list ordered by recency. Move accessed nodes to the front and evict from the back. Python's OrderedDict provides the same constant-time order operations.
Time & space
Expected O(1) time per operation and O(c) auxiliary space, where c is capacity.