Why is the input 2,[set(2,1),set(2,2),get(2),set(1,1),set(4,1),get(2)] expected [2,-1]?
I think it will get [2,2]. Because when set(4,1), key=2 was used 3 times, key=1 would be replaced.
LRU(Least Recently Used) would like to discard the least recently used items first.
What you are talking about is LFU(Least Frequency Used), which Counts how often an item is needed and those that are used least often are discarded first.