Is the expected result wrong in this case?


  • 1
    J

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

    The reason for my output:
    Key Value
    2 1
    1 1 get(2) == 1
    4 1 get(1) == 1, get(2) == -1 since 2 is not in the record


  • 1
    W

    When get(2) is called at the first time, (2,1) should be at the top of the cache. Then set(4, 1) is called, since the capacity is 2, the bottom item (1, 1) is popped at this time. Thus, when get(1) is called later, -1 should be returned.


  • 0
    J

    The bottom should be (2,1) since it's the first element, not (1,1), right?


  • 0
    W

    Just forget all the positions. After the first get(2) is called, then no doubt that (2, 1) is the most recently used item, and (1, 1) is the least recently used item at that time. Thus, a consequent set(4,1) should replace (1, 1), which is the least recently used.


  • 0
    J

    Now I see why. Thanks for your explanation.


Log in to reply
 

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