Is this test correct? If it is, then how to explain it?


  • 0
    Z

    Input: 2,[get(2),set(2,6),get(1),set(1,5),set(1,2),get(1),get(2)]
    Output: [-1,-1,2,-1]
    Expected: [-1,-1,2,6]


  • 1

    I think LRU cache updates the timestamp of a cache entry (when get or set) rather than writing a new entry with the same key value and insert it to the cache.

    LRU cache do parallel comparison on each entry's timestamp in hardware and kick out the one who has smallest timestamp value (least recently used).

    Therefore, the cache should be like:
    after set(2,6)
    [(2, 6), -]
    after set(1,5)
    [(1, 5), (2, 6)]
    after set(1,2)
    [(1, 2), (2, 6)]
    Please correct me if I'm wrong.


  • 1
    Z

    @RogerTsang Hi! Thanks for the reply, sounds very reasonable.


  • 0
    V

    I did not get it.
    before set(1, 2), (2, 6) should be least recently used, so (2, 6) should be invalidated and form [(1, 2), (1, 5)]. Why (1, 5) is pushed off?


  • 0
    V

    @vli02
    I guess it means to override the existing key/value if it sets with a duplicated key. This should explain it.
    I have a C code, will post it here.


Log in to reply
 

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