System Desgin

Posted on 2018-04-24 In Interview Views: Valine:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

系统设计

结构

来源

https://www.jianshu.com/p/f7cfd9dbcd5d

Scenario - Necessary - Application - Kilobit - Evolve

先说哪里用得到，再说我们需要解决问题多大规模。然后说基本解里头Application里面都有啥，然后说说相对应的数据放哪里怎么放。最后这些都说完了（20-25分钟左右）来具体谈怎么让我的基本解在哪些方面做的更好。

Scenario 场景

问清楚自己要做哪些功能（也就是说，45分钟内不聊哪些功能）
问清楚或者说清楚自己要handle多大用户量，面试官起码得给你确认这么几个信息，否则聊不下去。

一个是你平均每天handle多少用户
一个是你峰值（最多？不太精确但是形容一下）每天handle多少用户

自己把自己要算的东西都算出来， QPS啊，存储size啊，不非得一口气全部算完，但是记住最基本的用户量，然后再说然后的。

Trie 类型总结

Posted on 2018-04-22 In Leetcode Views: Valine:
Symbols count in article: 8.1k Reading time ≈ 7 mins.

Introduce to Trie

What is Trie

A Trie is a special form of a Nary tree. Typically, a trie is used to store strings. Each Trie node represents a string (a prefix). Each node might have several children nodes while the paths to different children nodes represent different characters. And the strings the child nodes represent will be the origin string represented by the node itself plus the character on the path.

How to represent

Dict

In Python we can use Dictionary to represent it, key is the char and value is the dict. It can save some space but slower because we need to calculate the hashcode every time.

class Trie(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = dict()
        
    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        curr = self.root
        for char in word:
            if char not in curr:
                curr[char] = dict()
            curr = curr[char]
        curr['#'] = '#'

用defalutdict会更加方便

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

Design 问题

Posted on 2018-03-22 In Leetcode Views: Valine:
Symbols count in article: 15k Reading time ≈ 13 mins.

Design系列问题

高频题

这类题基本上都是高频题

146. LRU Cache

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

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)

TopLogicalSort 总结

Posted on 2018-03-11 Edited on 2018-03-20 In Leetcode Views: Valine:
Symbols count in article: 4.8k Reading time ≈ 4 mins.

拓扑排序

拓扑排序适合于求解相关联的依赖状态，比如0依赖于1，2; 2 依赖于3
这样就类似于BFS的模版，用一个queue来维持；然后把各个链接用图的形式连接起来，从入度为0的点开始，遍历每一个字节点也就是每一个出度；同时对应的入度-1，如果对应的节点入度为0，证明该节点的依赖关系已经被计算过，从而加入Queue进行下一步操作

题目

模版

outdegree = [[] for _ in range(numCourses)]
indegree = [0 for _ in range(numCourses)]

queue = []
# find zero indegree

for i in indegree:
	if not i:
	queue.append(i)

count = 0
while queue:
	node = queue.pop(0)
	count += 1
	for succ in outdegree[course]:
		indegree[succ] -= 1
		# no indegree
		if indegree[succ] == 0:
			queue.append(succ)

DFS-BFS 总结

Posted on 2018-03-10 Edited on 2018-03-11 In Leetcode Views: Valine:
Symbols count in article: 7.2k Reading time ≈ 7 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

DFS

Matrix

介绍

对于不是Tree下面的DFS题来说，一直是我的一个弱点（不知道为什么），所以现在特意开贴来总结常见的题型

大致的模版就是明确dfs函数中不合法的状态要直接return和继续dfs的情况；同时也要做好visited的标记，从而避免无限循环的错误

def dfs(i,j,matrix):
	if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix) or matrix[i][j] == X:
		return

	# set visited
	matrix[i][j] = X
	dfs(i+1, j, matrix)
	dfs(i-1, j, matrix)
	...

Transmission Web Control

Posted on 2018-01-09 Edited on 2022-01-11 Views: Valine:
Symbols count in article: 5.1k Reading time ≈ 5 mins.

说明

本项目原作者为ronggang,
原托管于GitHub的transmission-web-control。但不知道原作者是否已经停止跟新，为方便大家使用，现新建一个repo并托管于此，欢迎大家反馈问题或者pull
request。

本项目主要目的是想加强Transmission Web的操作能力，本项目原本在Google Code托管，现迁移至GitHub。
本项目设计之初仅针对PT站，因此增加了 Tracker 服务器分组及状态，但这不并适用于普通BT种子。

English Introduction

支持的Transmission版本(Support Transmission Version)

Transmission 2.40 及以上版本（RPC版本：14及以上）
Transmission 2.40 and above (RPC version: 14 and above)

已修复问题

有时间的话我会尽量修改原repo里的问题，现在已经修改的问题如下：

更新了源程序的tar文件
修复英文界面的一些笔误
添加了http的安装方法
更新了install.sh的英文注释

功能介绍

在线查看Transmission当前工作情况；
在线添加新的种子文件或连接；
在线修改Transmission参数；
分页浏览方式加载种子；
多语言环境支持；
文件拖放添加种子；
删除指定的种子；
批量修改 Tracker；
移动指定种子的数据存放目录；
可按 Trackers 分组浏览；
其他……

Hello World!

Posted on 2018-01-09 Edited on 2022-01-11 Views: Valine:
Symbols count in article: 357 Reading time ≈ 1 mins.

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

Two Pointer问题总结

Posted on 2017-10-24 Edited on 2018-04-24 In Leetcode Views: Valine:
Symbols count in article: 3.4k Reading time ≈ 3 mins.

209. Minimum Size Subarray Sum

这道题没有那么多复杂的计算size方法，只是和大于k后，左移一位

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        # sliding widows
        if not nums:
            return 0
        l, r = 0, 0
        minLength = len(nums)+1
        res = 0
        while r < len(nums):
            res += nums[r]
            
            r += 1
            
            while res >= s:
                minLength = min(minLength, r - l)
                res -= nums[l]
                l += 1
        return 0 if minLength == len(nums)+1 else minLength

713. Subarray Product Less Than K

这道题甚至是上一道题的简略版本，要求出所有符合条件的。

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1: return 0
        prod = 1
        ans = left = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod /= nums[left]
                left += 1
            ans += right - left + 1
        return ans

763. Partition Labels

简化版本的windows题

class Solution(object):
    def partitionLabels(self, S):
        last = {c: i for i, c in enumerate(S)}
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            # update j like a sliding window
            j = max(j, last[c])
           
            if i == j:
                ans.append(i - anchor + 1)
                anchor = i + 1
            
        return ans

String总结

Posted on 2017-10-24 In Leetcode Views: Valine:
Symbols count in article: 1k Reading time ≈ 1 mins.

3. Longest Substring Without Repeating Characters

这道题就是用一个Dict来统计字符所出现的index，然后不断计算不重复字符串的长度

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        useddict = {}
        maxnum,start = 0,0
        for i in range(len(s)):
            if s[i] in useddict and start <= useddict[s[i]]:
                start = useddict[s[i]] + 1
            else:
                maxnum = max(maxnum, i - start + 1)
                
            useddict[s[i]]= i
        return maxnum

76. Minimum Window Substring

这题和之前的非常像，就是需要处理的边界条件很多

from collections import defaultdict
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not s:
            return ""
        if not t:
            return ""
        useddict = defaultdict(int)
        for char in t:
            useddict[char] += 1
        length = len(t)
        minnum,start,end = len(s)+1,0,0
        head = 0
        for i in range(len(s)):
            if s[i] in useddict:
                useddict[s[i]] -= 1
                if useddict[s[i]]>=0: 
                    length -= 1
                while length==0:
                    if i - start+1 < minnum:
                        minnum = i-start+1
                        head = start
                    if s[start] in useddict:
                        useddict[s[start]] += 1
                        if useddict[s[start]] > 0: ## more same char was used
                            length += 1
                    start += 1
                
        
        return s[head:head+minnum] if minnum <= len(s) else ""

Stack总结

Posted on 2017-10-24 Edited on 2017-10-27 In Leetcode Views: Valine:
Symbols count in article: 5k Reading time ≈ 5 mins.

Stack性质

定义

Stack的定义便是先进后出，在python中用list实现

class Stack(object):
	def __init__(self):
		self.stack = []
	def push(self, i):
		self.stack.append(i)
	def pop(self):
		if self.stack：
			return self.stack.pop()
		else:
			raise("Error")
	def peek(self):
		return self.stack[-1]

Basic 题目

225. Implement Stack using Queues

只用一个queue，每次append的时候，都要把前面的给pop出来再append进去

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()