LeetCode . Design a data structure supporting get(key) and put(key, value) in time. When the cache reaches capacity, evict the least recently used item before inserting a new one. Amazon asks this in nearly every onsite loop to test your design skills.
With capacity : put(1,1), put(2,2), get(1) returns 1, put(3,3) evicts key 2, get(2) returns -1.
A hash map gives you lookup. But how do you track which key was used least recently and remove it in ?
Constraints: , up to operations.