You are asked to design and implement a data structure that behaves similarly to an LRU (Least Recently Used) cache, but with a small variation:
capacity
.
Your data structure must support the following operations in average O(1) time:
get(key) -> value or -1
key
if it exists; otherwise return
-1
. Accessing a key counts as using it recently.
put(key, value)
key
. If inserting and the number of stored keys exceeds
capacity
, evict one key according to the modified eviction rule described above.
pin(key)
unpin(key)
Assume:
1 <= capacity <= 10^5
10^5
.
Describe the data structure you would use and implement the four operations with the required time complexity.