Is this test system give the wrong answer?

  • 1


    test: 2,[set(2,1),set(1,1),get(2),set(4,1),get(1),get(2)]

    And the result of the online judge system is: [1,-1,1]

    I just wonder about that when set the (4, 1), the record (2, 1) will be erased, but the online judge system signed that the pair (2, 1) still exist...


  • 0

    Because the problem asks to create a LRU cache and usage of an item is counted on set and get.

    • On set(2,1) the least recently used item is (2,1) (because it is the only one)
    • On set(1,1) the least recently used item is (2,1)
    • But then the test case executes get(2) so the least recently used item becomes (1, 1).
    • And when adding (4, 1), the capacity is exceeded and (1,1) is removed from the cache and the least recently used item becomes (2,1).

  • 0

    Oh, I got it....I misunderstand the proplem..Thanks a lot ^_^

  • 0

    I agree that the test case is wrong, strictly speaking, because the problem statement does not require get or set to update the recentness of those keys.

    It is, however, implicit in the name of LRU cache, that when you do get(2), that it becomes the most recent item, so that key 1 is erased when you do set(4,1).

    The specific requirements of get and set don't ask for this though, so the question is ambiguous.

Log in to reply

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