Please define what "used" means in this least recently used. Does insertion to cache for the very first time count as being used once? Please clarify the following 2 case:
- I keep on inserting different key-value pairs to the cache by calling set, then eventually cache reaches its capacity, and I need to invalidate.
set (2, 1)
set(100, 1) --> capacity is 99, capacity limit reached need to invalidate. So far, I never called get, so does it matter which entry I invalidate?
- I have a bunch of key-value pairs in the cache, the last entry before cache hits its capacity is a new entry. The next insertion to cache exceeds the capacity so cache needs to be invalidated, do I invalidate the most recently inserted entry because it was never used? Imagine I call get twice after inserting each new entry like this
set (2, 1)
set(99, 1) --> capacity is 99, the next call is NOT get(99)
set(100,1) --> which entry should be invalidated? (99,1) or (1, 1)?
"used" means "accessed", including both set and get. So in both of your two scenarios, you MUST invalidate (1, 1)
I have similar problems in understanding "least recently used."
For example: capacity is 2
The calling sequence is: set(2,1), set(2,2), get(2), set(1,1), set(4,1), get(2)
The correct answer by OJ is: [2, -1]
But the call "set(4,1)" should invalidate key=1, because key=2 has been used 3 times, and key=1 only one time. So I think the output should be [2,2]
Could anybody show me where I am being wrong?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.