Test Case Seems Wrong

  • 2

    I think the following test case seems incorrect. This test case seems to be picking a recently "set" item over a less recently "get" item for eviction.

    set 1,1
    set 2,2
    get 2
    get 1
    get 2
    set 3,3 <-- 3,3 is now more recent than 2,2 or 1,1 (However, the test case seems to be imply the opposite.)

    Or am I missing something?


  • 2

    Among 6 operations (set and get) to get your cache full before evict, '3' is accessed one time. Thus, it will be evicted when you set 4,4

  • 3

    It's a LFU(Least Frequently Used) cache and ur output show me that u deal the problem as a LRU(Least Recently Used) cache.

    When the key 4 is setted, the key 1 has been used twice, the key 2 has been used three times and the key 3 has been used only once, so we delete the key 3 to add the key 4 to the cache.


  • 0

    @Mxxx Oh. Ok. You are correct. I was thinking Least Recently Used, not Least Frequently Used. My bad. Thanks.

Log in to reply

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