Design 问题

Posted on | In | Comments: | Views: | Views:
Symbols count in article: 22k | Reading time ≈ 20 mins.

Design系列问题

高频题

这类题基本上都是高频题

146. LRU Cache

这道题是很高频的题目，主要hint就是用双向链表来实现

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
class Node:
	def __init__(self, k, v):
		self.key = k
		self.val = v
		self.prev = None
		self.next = None
class LRUCache(object):

    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:
            n = self.dic[key]
            self._remove(n)
            self._add(n)
            return n.val
        return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.dic:
            self._remove(self.dic[key])
        n = Node(key, value)
        self._add(n)
        # imp value - node
        self.dic[key] = n
        if len(self.dic) > self.capacity:
            n = self.head.next
            self._remove(n)
            del(self.dic[n.key])
            
    def _add(self, node):
        p = self.tail.prev
        p.next = node
        self.tail.prev = node
        node.prev = p
        node.next = self.tail
        
        
    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p

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

155. Min Stack

这道题就是用stack来存sofar的最小值

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
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if len(self.stack) == 0:
            self.stack.append((x,x))
        else:
            min_sofar = min(x, self.stack[-1][1])
            self.stack.append((x, min_sofar))

    def pop(self):
        """
        :rtype: void
        """
        self.stack.pop()  

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1][0]

    def getMin(self):
        """
        :rtype: int
        """
        return self.stack[-1][1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

716. Max Stack

与上一道题相类似，区别就是在popMax的时候用临时stack来记录

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
class MaxStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        maxNumber = max(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x,maxNumber))

    def pop(self):
        """
        :rtype: int
        """
        return self.stack.pop()[0]
        

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1][0]
        

    def peekMax(self):
        """
        :rtype: int
        """
        return self.stack[-1][1]
        

    def popMax(self):
        """
        :rtype: int
        """
        temp = self.stack[-1][1]
        tempStack = []
        
        while self.stack[-1][0] != temp:
            tempStack.append(self.stack.pop())
        self.stack.pop()
        while tempStack:
            self.push(tempStack.pop()[0])
      
        return temp
        


# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()

225. Implement Stack using Queues

在init的时候，每当新元素进来的时候，不断让queue的元素pop出来在加到queue尾，从而index为0 的元素就是最后加进来的

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
class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []
        

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.queue.append(x)
        size = len(self.queue)
        while size > 1:
            self.queue.append(self.queue.pop(0))
            size -= 1
        

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.queue.pop(0)
        

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.queue[0]
        

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return len(self.queue) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

232. Implement Queue using Stacks

用两个stack，在pop的时候，也是同样的像上一题的操作，加到另外一个stack中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyQueue(object):
    def __init__(self):
        self.input = []
        self.output = []
        
    def push(self, x):
        self.input.append(x)

    def pop(self):
        self.peek()
        return self.output.pop()
        
    def peek(self):
        if(self.output == []):
            while(self.input != []):
                self.output.append(self.input.pop())
        return self.output[-1]
        
    def empty(self):
        return self.input == [] and self.output == []

297. Serialize and Deserialize Binary Tree

这道题就是BFS遍历树，然后BFS解析树，注意index的值

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ""
        queue = [root]
        res = []
        while queue:
            node = queue.pop(0)
            if node:
                queue.append(node.left)
                queue.append(node.right)
            res.append(str(node.val) if node else "#")
        # strip left ','
        return ",".join(res).strip(',')
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        nodes = []
        for i in data.split(","):
            if i != '#':
                nodes.append(TreeNode(i))
            else:
                nodes.append(None)
        
        queue = [nodes[0]]
        index = 1
        while queue:
            node = queue.pop(0)
            if index < len(nodes) and nodes[index]:
                node.left = nodes[index]
                queue.append(nodes[index])
            if index + 1 < len(nodes) and nodes[index+1]:
                node.right = nodes[index+1]
                queue.append(nodes[index+1])
            index += 2
            
        return nodes[0]
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

173. Binary Search Tree Iterator

这道题也是高频题，FB面过.注意pushAll的时候是判断root！

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
# Definition for a  binary tree node
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.pushAll(root)
        
    def pushAll(self,root):
        while root:
            self.stack.append(root)
            root = root.left
            
    def hasNext(self):
        """
        :rtype: bool
        """
        return self.stack
        

    def next(self):
        """
        :rtype: int
        """
        node = self.stack.pop()
        
        self.pushAll(node.right)
        return node.val
        

# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

380. Insert Delete GetRandom O(1)

用dic来记录value和对应的index，从而能保证O（1）时间内删除

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
import random
class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.array = []
        self.dic = dict()

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.dic:
            return False
        self.dic[val] = len(self.array)
        self.array.append(val)
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.dic:
            return False
        # val.index in self.array
        index = self.dic[val]
        
        # check not the last
        if index < len(self.array) - 1:
            last = self.array[-1]
            self.dic[last] = index
            self.array[index] = last
            
        self.array.pop()
        del(self.dic[val])
        return True
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return self.array[random.randint(0, len(self.array)-1)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

381. Insert Delete GetRandom O(1) - Duplicates allowed

dic里面的值用set来记录

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
import random
class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.array = []
        self.dic = dict()

    def insert(self, val):
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        
        if val not in self.dic:
            self.dic[val] = set()
            self.dic[val].add(len(self.array))
            self.array.append(val)
            return True
        else:
            self.dic[val].add(len(self.array))
            self.array.append(val)
            
            return False

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.dic:
            return False
        
        # val.index in self.array
        index = self.dic[val].pop()
        
        if index < len(self.array) - 1:
            
            last = self.array[-1]
            self.array[index] = last
            # last item delete
            # remove old insert new
            
            self.dic[last].remove(len(self.array)-1)
            self.dic[last].add(index)
            
        self.array.pop()
        if not self.dic[val]:
            del(self.dic[val])
        return True
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return self.array[random.randint(0, len(self.array)-1)]


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

Trie类型

简单构建

在程序中需要简单构建一个Trie

1
2
3
4
5
6
7
8
trie = {}
for w in words:
    t = trie
    for c in w:
        if c not in t:
            t[c] = {}
        t = t[c]
    t['#'] = '#'

208. Implement Trie (Prefix 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
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
from collections import defaultdict
class TrieNode(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nodes = defaultdict(TrieNode)  # Easy to insert new node.
        self.isword = False  # True for the end of the trie.
class Trie(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        curr = self.root
        for char in word:
            curr = curr.nodes[char]
        curr.isword = True
        

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        curr = self.root
        for char in word:
            if char not in curr.nodes:
                return False
            else:
                curr = curr.nodes[char]
        return curr.isword
        

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        curr = self.root
        for char in prefix:
            if char not in curr.nodes:
                return False
            else:
                curr = curr.nodes[char]
        return True
        
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

211. Add and Search Word - Data structure design

如何处理. 的问题，用string的slice来搞，find的递归操作

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
from collections import defaultdict
class TrieNode(object):
    def __init__(self):
        self.node = defaultdict(TrieNode)
        self.isWord = False

    def __repr__(self):
        return repr(self.node)
        
class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        curr = self.root
        for char in word:
            curr = curr.node[char]
        curr.isWord = True
        

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        return self.find(self.root, word)
    
    def find(self, trie, word):
        if word == '':
            return trie.isWord
        
        if word[0] == '.':
            for i in trie.node:
                if self.find(trie.node[i], word[1:]):
                    return True
        else:
            child = trie.node.get(word[0])
            if child:
                return self.find(child, word[1:])
        return False

642. Design Search Autocomplete System

进阶版本 取前三个。很复杂的题

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
class TrieNode(object):
    def __init__(self):
        self.children = dict()
        self.isEnd = False
        self.rank = 0
        self.data  = None
        
class AutocompleteSystem(object):

    def __init__(self, sentences, times):
        """
        :type sentences: List[str]
        :type times: List[int]
        """
        self.root = TrieNode()
        self.keyword = ""
        for i, sentence in enumerate(sentences):
            self.addRecord(sentence, times[i])
            
    def addRecord(self, word, rank):
        p = self.root
        for char in word:
            if char not in p.children:
                p.children[char] = TrieNode()
            p = p.children[char]
        p.isEnd = True   
        p.data = word
        # compare
        p.rank -= rank
        

    def search(self, word):
        p = self.root
        for char in word:
            if char not in p.children:
                return []
            p = p.children[char]
        return self.dfs(p)
    
    def dfs(self, root):
        res = []
        if root:
            # find the end
            if root.isEnd:
                res.append((root.rank, root.data))
            for child in root.children:
                res.extend(self.dfs(root.children[child]))
        return res
    
    def input(self, c):
        """
        :type c: str
        :rtype: List[str]
        """
        res = []
        if c != "#":
            self.keyword += c
            res = self.search(self.keyword)
        else:
            self.addWord(self.keyword,1)
            self.keyword = ""
        return [item[1] for item in sorted(res)[:3]]
        


# Your AutocompleteSystem object will be instantiated and called as such:
# obj = AutocompleteSystem(sentences, times)
# param_1 = obj.input(c)

一般的题

281. Zigzag Iterator

就是正常的来

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
class ZigzagIterator(object):

    def __init__(self, v1, v2):
        """
        Initialize your data structure here.
        :type v1: List[int]
        :type v2: List[int]
        """
        self.res = []
        pos = 0
        while pos < max(len(v1), len(v2)):
            if pos < len(v1):
                self.res.append(v1[pos])
            if pos < len(v2):
                self.res.append(v2[pos])
            pos += 1
        self.index = 0
        

    def next(self):
        """
        :rtype: int
        """
        res = self.res[self.index]
        self.index += 1
        return res
        

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.index < len(self.res)
        

# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())

284. Peeking Iterator

先预存next的值

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
# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator(object):
#     def __init__(self, nums):
#         """
#         Initializes an iterator object to the beginning of a list.
#         :type nums: List[int]
#         """
#
#     def hasNext(self):
#         """
#         Returns true if the iteration has more elements.
#         :rtype: bool
#         """
#
#     def next(self):
#         """
#         Returns the next element in the iteration.
#         :rtype: int
#         """

class PeekingIterator(object):
    def __init__(self, iterator):
        self.iter = iterator
        self.temp = self.iter.next() if self.iter.hasNext() else None

    def peek(self):
        return self.temp

    def next(self):
        ret = self.temp
        self.temp = self.iter.next() if self.iter.hasNext() else None
        return ret

    def hasNext(self):
        return self.temp is not None
        

# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
#     val = iter.peek()   # Get the next element but not advance the iterator.
#     iter.next()         # Should return the same value as [val].

359. Logger Rate Limiter

window的size为10

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
class Logger(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = dict()
        

    def shouldPrintMessage(self, timestamp, message):
        """
        Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity.
        :type timestamp: int
        :type message: str
        :rtype: bool
        """
        # condition one 
        if message in self.dic and timestamp - self.dic[message] < 10:
            return False
        else:
            self.dic[message] = timestamp
            return True


# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp,message)

362. Design Hit Counter

因为是统计当时的hit值，所以可以维护一个全局变量hit

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
class HitCounter(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.count = 0
        self.queue = []

    def hit(self, timestamp):
        """
        Record a hit.
        @param timestamp - The current timestamp (in seconds granularity).
        :type timestamp: int
        :rtype: void
        """
        if not self.queue or self.queue[-1][0] != timestamp:
            self.queue.append([timestamp,1])
        else:
            self.queue[-1][1] += 1
        self.count += 1
        
    def getHits(self, timestamp):
        """
        Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity).
        :type timestamp: int
        :rtype: int
        """
        # move forward
        while self.queue and timestamp - self.queue[0][0] >= 300:
            self.count -= self.queue.pop(0)[1]
        return self.count


# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)
Donate comment here