The description of this task confuses me


  • 1
    L

    how to explain these two test data

    input 2,[set(2,1),set(1,1),get(2),set(4,1),get(1),get(2)]

    output [1,-1,1]

    and

    input 2,[set(2,1),set(2,2),get(2),set(1,1), set(4,1),get(2)]

    output [2,-1]

    set means used? or get means used? or both?


  • 7
    M

    Both set and get are "used", though get not in every case. Set will always change the queue, by changing a value of something in it and moving it to the end, or by adding to the cache and possibly removing the least recently used term. Either way, the term being set was used. Get only is "used" when it is in the cache already. If it is not, it simply returns -1 and does not change the queue. When it is in the queue, the pair is used and so moves to the end of the queue.

    As an example, here is the running of the first test data, which involves three of the four cases.

    It's an lru cache, so the first term, the int, is the capacity. The second term, the list, is a series of methods being called. In the first example, it creates an lru cache with size 2, then sets the value 1 for key 2, sets the value 1 for key 1. At this point, the lru queue looks like this:

    [(2,1),(1,1)]
    

    The next command, get(2), returns 1, its value, and means that (2,1) is now more recently used, so gets moved to the end of the queue:

    [(1,1),(2,1)]
    

    The next, set(4,1) adds (4,1) to the cache, but it is at capacity, so the Least Recently Used term, (1,1) is removed from the cache to provide space. The queue now looks like this:

    [(2,1),(4,1)]
    

    The next two commands are get(1) and get(2). The key 1 was removed by that last step, so it returns -1, the term for "not in cache". Nothing changes in the queue. get(2), on the other hand, is in the queue, so returns 1, its value, and moves to the end of the queue. The queue now looks like this:

    [(4,1),(2,1)]
    

    But that doesn't really matter, since that is the last of the commands.

    As you can see in my answer, the commands return 1, then -1, then 1. Composed as a list, it looks like this:

    [1,-1,1]
    

    Oh look, it's the provided output.


  • 0
    L

    Thank you for your clear answer. Now I can understand.
    For set operation, if it is not at capacity, set a pair to the end of queue, and it means the pair is most recently. if capacity, pop the first of the queue and set pair to the end.
    For get operation, the order of the queue will be changed by getting if the key in the queue.


  • 0
    E

    input 2,[set(2,1),set(2,2),get(2),set(1,1), set(4,1),get(2)]

    output [2,-1] Is this correct?

    After "set(2,1),set(2,2)", get(2) gives us 2. But after "set(1,1), set(4,1)", get(2) gives us -1? set(1,1) will place 1 in the cache, then after set(4,1), 4 replaces 2 in the cache? Why 2 is replaced?

    I think I got it. It is to replace the least recently visited, not the least visited.


Log in to reply
 

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