[LeetCode] 146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Thought process:
Use a linked list to store the values and their orders in the cache. Use a hash map to map keys to list node. The linked list's order will be changing constantly. Get operation move the value requested to to head/tail of the list, to represent that it's most recently used. Put operation will sometimes require the tail/head list node to be removed.
To satisfy the above cases, I have two options:
  1. Use a doubly linked list, and map key directly to its corresponding node.
  2. Use a singly linked list, and map key to the previous node.
Using a singly-linked list:
  1. Get: check map.
    1. Key exists: move value to tail of the list. Return value.
    2. Key doesn't exist: return -1.
  2. Put:
    1. Key exists: set to new value, and move the node to the most recently used direction.
    2. Key doesn't exist:
      1. Insert node to the most recently used position.
      2. If capacity is exceeded, evict the least recently used item (head of list).

Solution 1 (singly-linked list):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public class LRUCache {
    private class ListNode {
        int key;
        int value;
        ListNode next;
        ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private ListNode dummy;
    private ListNode tail;
    private Map<Integer, ListNode> map;
    private int capacity;

    public LRUCache(int capacity) {
        dummy = new ListNode(0, 0);
        tail = dummy;
        map = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            ListNode previous = map.get(key);
            moveToTail(previous);
            
            return tail.value;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode previous = map.get(key);
            previous.next.value = value;
            moveToTail(previous);
        } else {
            if (map.size() == capacity) {
                map.remove(dummy.next.key);
                dummy.next = dummy.next.next;
                if (dummy.next != null) {
                    map.put(dummy.next.key, dummy);
                }
            }
            ListNode put = new ListNode(key, value);
            tail.next = put;
            map.put(key, tail);
            tail = put;
        }
    }
    
    private void moveToTail(ListNode previous) {
        ListNode got = previous.next;
        if (got == tail) {
            return;
        }
        
        previous.next = got.next;
        if (previous.next != null) {
            map.put(previous.next.key, previous);
        }
        
        tail.next = got;
        got.next = null;
        map.put(got.key, tail);
        tail = got;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Solution 2 (doubly-linked list):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public class LRUCache {
    class ListNode {
        int key;
        int value;
        ListNode previous;
        ListNode next;
        
        ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private ListNode head;
    private ListNode tail;
    private Map<Integer, ListNode> map;
    private int capacity;
    private int size;
    
    public LRUCache(int capacity) {
        head = new ListNode(0, 0);
        tail = new ListNode(0, 0);
        head.next = tail;
        tail.previous = head;
        map = new HashMap<>();
        this.capacity = capacity;
        size = 0;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        ListNode node = map.get(key);
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (size == capacity) {
                evict();
                size--;
            }
            insert(key, value);
        }
    }
    
    private void moveToHead(ListNode node) {
        deleteNode(node);
        addToHead(node);
    }
    
    private void evict() {
        ListNode lru = tail.previous;
        deleteNode(lru);
        map.remove(lru.key);
    }
    
    private void insert(int key, int value) {
        ListNode node = new ListNode(key, value);
        addToHead(node);
        map.put(key, node);
        size++;
    }
    
    private void addToHead(ListNode node) {
        ListNode next = head.next;
        head.next = node;
        node.previous = head;
        node.next = next;
        next.previous = node;
    }
    
    private void deleteNode(ListNode node) {
        node.previous.next = node.next;
        node.next.previous = node.previous;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Time complexity: O(1) for both get and put.
Location: San Jose, CA, USA

Comments

Post a Comment

Popular posts from this blog

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers  prices , for which the  i -th element is the price of a given stock on day  i ; and a non-negative integer  fee  representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.) Return the maximum profit you can make. Example 1: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: Buying at prices[0] = 1 Selling at prices[3] = 8 Buying at prices[4] = 4 Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Note: 0 < prices.length <= 50000 . 0 < prices[i] < 50000 . 0 <= fee < 50000 . Thought process: Each day there are two options, buy or sell. Use two variables buy and sell to keep track of the max profit. Solutio...
Read more

[LeetCode] 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of  non-empty  words from the dictionary, where  words are sorted lexicographically by the rules of this new language . Derive the order of letters in this language. Example 1: Given the following words in dictionary, [ "wrt", "wrf", "er", "ett", "rftt" ] The correct order is:  "wertf" . Example 2: Given the following words in dictionary, [ "z", "x" ] The correct order is:  "zx" . Example 3: Given the following words in dictionary, [ "z", "x", "z" ] The order is invalid, so return  "" . Note: You may assume all letters are in lowercase. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary. If the order is invalid, return an empty string...
Read more

[LeetCode] 631. Design Excel Sum Formula

Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions: Excel(int H, char W):  This is the constructor. The inputs represents the height and width of the Excel form.  H  is a positive integer, range from 1 to 26. It represents the height.  W  is a character range from 'A' to 'Z'. It represents that the width is the number of characters from 'A' to  W . The Excel form content is represented by a height * width 2D integer array  C , it should be initialized to zero. You should assume that the first row of  C  starts from 1, and the first column of  C  starts from 'A'. void Set(int row, char column, int val):  Change the value at  C(row, column)  to be val. int Get(int row, char column):  Return the value at  C(row, column) . int Sum(int row, char column, List of Strings : numbers):  This function...
Read more