Design and implement a data structure that supports an LRU (Least Recently Used) cache with a fixed capacity.
Implement a cache with the following operations:
get(key) -> value
key
exists in the cache, return its value and mark the entry as
most recently used
.
key
does not exist, return
-1
.
put(key, value) -> void
(key, value)
pair.
capacity
, evict the
least recently used
entry.
get
and
put
.
Assume capacity = 2:
put(1, 10)
put(2, 20)
get(1) -> 10
(now key
1
is most recently used)
put(3, 30)
(evicts key
2
as least recently used)
get(2) -> -1
You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.