Please define least recently used, does insertion to cache count as used?


  • 11
    P

    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:

    1. 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(1, 1)
      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?
    1. 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(1, 1)
    get(1)
    get(1)
    set (2, 1)
    get(2)
    get(2)
    ....
    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)?


  • 3
    S

    "used" means "accessed", including both set and get. So in both of your two scenarios, you MUST invalidate (1, 1)


  • 0
    H

    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?


  • 0
    M

    Hitalex - This is least recently used cache eviction algorithm. Your answer would be right if it is least FREQUENTLY used (LFU) algorithm where the number of times the key is accessed matters. It does not matter in LRU.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.