[Leetcode] Design

Posted on | In , |

146. LRU Cache

Leetcode: https://leetcode.com/problems/lru-cache/description/

Video: https://www.youtube.com/watch?v=q1Njd3NWvlY&t=28s

[Solution]

  • Use two layers of datastructure
  • First layer: Dict (HashTable), store key-value pairs
  • Second layer: Doubly Linked List, to realize remove tail and insert head in O(1) time
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
# Define node
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dic = {}
        self.head = Node(0,0)
        self.tail = Node(0,0)
        self.head.next = self.tail
        self.tail.prev = self.head
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.dic:
            # Put key in head of the list
            n = self.dic[key]
            self._remove(n)
            self._add(n)
            return n.val
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        # if key in dict: move node to the front
        if key in self.dic:
            n = self.dic[key]
            self._remove(n)
            new = Node(key, value)
            self._add(new)
        else:
            # if key not in dict
            if len(self.dic) >= self.capacity:
                # if reach to capacity
                # remove the tail node
                n = self.tail.prev
                self._remove(n)
                
            # add new node into system 
            new = Node(key, value)
            self._add(new)
        
    def _add(self, node):
        """
        Insert node in front of the linkedlist
        Insert the key into the dict
        """
        n = self.head.next
        self.head.next = node
        node.next = n
        node.prev = self.head
        n.prev = node
        self.dic[node.key] = node
        
    def _remove(self, node):
        """
        Remove the node from the it's position
        Remove key from the dict
        """
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p
        del self.dic[node.key]

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

284. Peeking Iterator

Leetcode: https://leetcode.com/problems/peeking-iterator/description/

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
class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iter = iterator
        self.has = self.iter.hasNext()
        self.nxt = self.iter.next() if self.iter.hasNext() else None

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        return self.nxt

    def next(self):
        """
        :rtype: int
        """
        n = self.nxt
        self.nxt = self.iter.next() if self.iter.hasNext() else None
        return n

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.nxt is not None

173. Binary Search Tree Iterator

Leetcode: https://leetcode.com/problems/binary-search-tree-iterator/description/
[Solution] Use a stack to store left child of binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class BSTIterator:

    def __init__(self, root):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left
        

    def next(self):
        n = self.stack.pop()
        if n.right:
            r = n.right
            while r:
                self.stack.append(r)
                r = r.left
        return n.val

    def hasNext(self):
        """
        @return whether we have a next smallest number
        """
        return len(self.stack) != 0

Generator solution (not quite understand)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def __init__(self, root):
    self.last = root
    while self.last and self.last.right:
        self.last = self.last.right
    self.current = None
    self.g = self.iterate(root)

# @return a boolean, whether we have a next smallest number
def hasNext(self):
    return self.current is not self.last

# @return an integer, the next smallest number
def next(self):
    return next(self.g)
    
def iterate(self, node):
    if node is None:
        return
    for x in self.iterate(node.left):
        yield x
    self.current = node
    yield node.val
    for x in self.iterate(node.right):
        yield x

Note:

  1. Remember to deal with root = None
  2. Use self.last == self.current to detect if we reach to the end of the tree
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
class BSTIterator(object):

    def __init__(self, root):
        self.current = None
        self.last = root
        
        while self.last and self.last.right:
            self.last = self.last.right
            
        def generator(root): # Iterative method of in-order traversal
            stack = []
            cur = root
            while True:
                while cur:
                    stack.append(cur)
                    cur = cur.left
                if not cur and stack:
                    top = stack.pop()
                    self.current = top
                    yield top
                    cur = top.right
                if not cur and not stack:
                    break
                    
        self.g = generator(root)

    def next(self):
        return next(self.g).val

    def hasNext(self):
        return self.current is not self.last

642. Design Search Autocomplete System

155. Min Stack

Leetcode: https://leetcode.com/problems/min-stack/

Note:

  • The tricky part is to get the min after pop operation, if the popped element was min, then we should update min with the second minimum number.
  • So when we pushing elements into the stack, if x is smaller than the current min, we append the current min to the stack as a snapshot of the previous minimum number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = float('inf')

    def push(self, x: int) -> None:
        if x <= self.min:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)

    def pop(self) -> None:
        top = self.stack.pop()
        if top == self.min:
            self.min = self.stack.pop() # pop twice to get the previous min before top

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min

706. Design HashMap

Leetcode: https://leetcode.com/problems/design-hashmap/

My solution: since the problem limits the input length < 100000, I just set an initial array with length = 100000.
Chain solution: (https://leetcode.com/problems/design-hashmap/discuss/185347/Hash-with-Chaining-Python)

  • Use an array of length 1000 with a linkedlist in each cell
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
class Node:
    def __init__(self, key, value):
        self.pair = (key, value)
        self.next = None
        
class MyHashMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.n = 1000
        self.m = [None] * self.n

    def put(self, key: int, value: int) -> None:
        """
        value will always be non-negative.
        """
        index = key % self.n
        if self.m[index] == None: # create
            self.m[index] = Node(key, value)
        else: # update
            head = self.m[index]
            while True:
                if key == head.pair[0]:
                    head.pair = (key, value) # update
                    break
                elif head.next == None:
                    head.next = Node(key, value)
                    break
                head = head.next

    def get(self, key: int) -> int:
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        """
        index = key % self.n
        head = self.m[index]
        while head:
            if head.pair[0] == key:
                return head.pair[1]
            head = head.next
        return -1

    def remove(self, key: int) -> None:
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        """
        index = key % self.n
        head = self.m[index]
        if head and head.pair[0] == key:
            self.m[index] = head.next
            return
        prev = head
        while head and head.pair[0] != key:
            prev = head
            head = head.next
        if head:
            prev.next = head.next
            return

348. Design Tic-Tac-Toe

Leetcode: https://leetcode.com/problems/design-tic-tac-toe/

My solution (pretty slow): use a map to keep track of the count of each player on every columns, rows, and diagnoses.

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
var TicTacToe = function(n) {
    this.board = new Array(n).map(row => new Array(n).fill(0));
    this.map = new Map();
    this.status = 0; // 0: no one, 1: player 1 wins, 2: player 2 wins
};

TicTacToe.prototype.updateStatus = function() {
    for (let k of this.map.keys()) { // 1#_1
        if (this.map.get(k) == this.board.length) {
            return parseInt(k[0])
        }
    }
    return 0;
}
/**
 * Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. 
 * @param {number} row 
 * @param {number} col 
 * @param {number} player
 * @return {number}
 */
TicTacToe.prototype.getLines = function(row, col, player) {
    let basic = player.toString() + "#";
    let res = [basic + row.toString() + "_", basic + "_" + col.toString()];
    if (row === col) {
        res.push(basic + "(");
    } 
    if (row + col === this.board.length - 1) {
        res.push(basic + ")");
    }
    return res;
}

TicTacToe.prototype.move = function(row, col, player) {
    if (this.status !== 0) { return this.status; }
    let lines = this.getLines(row, col, player);
    for (let l of lines) {
        if (this.map.has(l)) {
            this.map.set(l, this.map.get(l) + 1);
        } else {
            this.map.set(l, 1);
        }
    }
    
    this.status = this.updateStatus();
    return this.status;
};

O(1) Solution: when is player 1 we + 1, else we - 1, and see if any of the rows, cols, or diagnoses reach to n or -n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var TicTacToe = function(n) {
    this.rows = new Array(n).fill(0);
    this.cols = new Array(n).fill(0);
    this.diag = 0;
    this.andiag = 0;
};
TicTacToe.prototype.move = function(row, col, player) {
    let toAdd = player === 1 ? 1 : -1;
    this.rows[row] += toAdd;
    this.cols[col] += toAdd;
    if (row === col) { this.andiag += toAdd; }
    let n = this.rows.length;
    if (row + col === n - 1) { this.diag += toAdd; }
    if (Math.abs(this.rows[row]) === n || Math.abs(this.cols[col]) === n || Math.abs(this.andiag) == n || Math.abs(this.diag) == n) { return player; }
    return 0
};

362. Design Hit Counter

Leetcode: https://leetcode.com/problems/design-hit-counter/

Solution:

  1. Use 2 buckets with length 300, use times bucket to record the closest timestamp on the index, use hits bucket to record the hit numbers
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
class HitCounter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.times = [0 for _ in range(300)]
        self.hits = [0 for _ in range(300)]

    def hit(self, timestamp: int) -> None:
        """
        Record a hit.
        @param timestamp - The current timestamp (in seconds granularity).
        """
        index = timestamp % 300
        
        if self.times[index] == timestamp:
            # multiple hits on same timestamp
            self.hits[index] += 1
        else:
            self.hits[index] = 1
        self.times[index] = timestamp # record the closest time bucket got hit

    def getHits(self, timestamp: int) -> int:
        """
        Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity).
        """
        hits = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                hits += self.hits[i]
        return hits