KK's blog

LeetCode

Android devices have a special lock screen with a 3 x 3 grid of dots. Users can set an “unlock pattern” by connecting the dots in a specific sequence, forming a series of joined line segments where each segment’s endpoints are two consecutive dots in the sequence. A sequence of k dots is a valid unlock pattern if both of the following are true:

All the dots in the sequence are distinct. If the line segment connecting two consecutive dots in the sequence passes through the center of any other dot, the other dot must have previously appeared in the sequence. No jumps through the center non-selected dots are allowed.
For example, connecting dots 2 and 9 without dots 5 or 6 appearing beforehand is valid because the line from dot 2 to dot 9 does not pass through the center of either dot 5 or 6. However, connecting dots 1 and 3 without dot 2 appearing beforehand is invalid because the line from dot 1 to dot 3 passes through the center of dot 2.

Here are some example valid and invalid unlock patterns:



The 1st pattern [4,1,3,6] is invalid because the line connecting dots 1 and 3 pass through dot 2, but dot 2 did not previously appear in the sequence. The 2nd pattern [4,1,9,2] is invalid because the line connecting dots 1 and 9 pass through dot 5, but dot 5 did not previously appear in the sequence.
The 3rd pattern [2,4,1,3,6] is valid because it follows the conditions. The line connecting dots 1 and 3 meets the condition because dot 2 previously appeared in the sequence. The 4th pattern [6,5,4,1,9,2] is valid because it follows the conditions. The line connecting dots 1 and 9 meets the condition because dot 5 previously appeared in the sequence.

Given two integers m and n, return the number of unique and valid unlock patterns of the Android grid lock screen that consist of at least m keys and at most n keys.

Two unlock patterns are considered unique if there is a dot in one sequence that is not in the other, or the order of the dots is different.

Example 1:

Input: m = 1, n = 1
Output: 9

Example 2:

Input: m = 1, n = 2
Output: 65

Constraints:

* 1 <= m, n <= 9

题目大意：

安卓开屏密码解锁种数。给定m, n是安卓的密码长度范围，求这个范围内的解码种数。1可以跳到2和4, 5, 6, 8(斜线没有通过其他数字)，但不能跳到3, 7, 9因为前提条件是这条线通过的数如2, 4, 5必须已经用过了。

解题思路：

此题属于填位法，带条件的，条件在于map中，类似于LeetCode 248 Strobogrammatic Number III
难点是理解jump keys，有16种

1
2
3
4
5

skip[1][3] = skip[3][1] = 2;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;
skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;

解题步骤：

用DFS模板: def dfs(self, graph, start, visited, res), start = num

注意事项：

1. Line 9有return，所以要去掉刚加入的visited的num

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

JUMP_KEYS = {(1,3):2, (1,7):4, (1,9):5, (2,8):5, (3,7):5, (3,1):2, (3,9):6, (4,6):5, (6,4):5, (7,1):4, (7,3):5, (7,9):8, (8,2):5, (9,7):8, (9,3):6, (9,1):5}
class Solution(TestCases):

    def dfs(self, num, m, n, visited):
        if num in visited:
            return 0
        visited.add(num)
        if len(visited) == n:
            visited.remove(num) # remember
            return 1
        res = 0
        if len(visited) >= m:
            res += 1
        for next_num in range(1, 10):
            if (num, next_num) in JUMP_KEYS and JUMP_KEYS[(num, next_num)] not in visited:
                continue
            res += self.dfs(next_num, m, n, visited)
        visited.remove(num)
        return res

算法分析：

时间复杂度为O(1)，空间复杂度O(1), 因为最多是9乘以8乘以7…

LeetCode

Input: expression = “e + 8 - a + 5”, evalvars = [“e”], evalints = [1]
Output: [“-1a”,”14”]

Input: expression = “e - 8 + temperature - pressure”, evalvars = [“e”, “temperature”], evalints = [1, 12]
Output: [“-1pressure”,”5”]

Input: expression = “(e + 8)  (e - 8)”, evalvars = [], evalints = []
Output: [“1ee”,”-64”]

题目大意：

表达式含有若干变量evalvars及其对应值evalints，且含加减乘和括号，求结果。若变量不在evalvars就简化表达式

解题思路：

此题不需要掌握，若考到就认命好了。之前的LeetCode 224 Basic Calculator含有括号和加法已经是Hard，此题不但有括号和加减乘，还有变量，难度不止提高一个数量级。不过不可以用eval函数的条件去掉了。所以就是考察eval。
如果不含变量，直接调用eval即可求解

Python代码：

1
2

def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	return eval(expression)

含变量且变量有值，就调用字典将变量替代掉，这里考到了regex替代函数re.sub

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	var_to_val = dict(zip(evalvars, evalints))

	def f(s):
		token = s.group()
		s = str(var_to_val[token] if token in var_to_val else token)
		return s

	converted_expr = re.sub(r'\w+', f, expression)
	res = eval(converted_expr)
	return res

由于变量可能没有值，所以核心思路是用dict进行计算，如x + 2，用集合求和{(x,): 1} + {(): 2}得到{(‘x’,): 1, (): -2}，用dict来计算及保存结果

解题步骤：

1. regex替代变量
2. 将表达式用f包装，如(f(“x”) + f(“8”)) * (f(“x”) - f(“8”))
3. 实现dict的加减乘
4. dict的计算结果转成题目所求

注意事项：

1. Python代码：

   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

   def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]: class MyCounter(Counter): def __add__(self, other): self.update(other) return self def __sub__(self, other): self.subtract(other) return self def __mul__(self, other): product = MyCounter() for x in self: for y in other: xy = tuple(sorted(x + y)) product[xy] += self[x] * other[y] return product var_to_val = dict(zip(evalvars, evalints)) def f(s): token = s s = str(var_to_val[token] if token in var_to_val else token) return MyCounter({(s, ): 1}) if s.isalpha() else MyCounter({(): int(s)}) converted_expr = re.sub(r'(\w+)', r'f("\1")', expression) # (f("x") + f("8")) * (f("x") - f("8")) res = eval(converted_expr) # # C({('x', 'x'): 1, ('x',): 0, (): -64}) return ['*'.join((str(res[x]), ) + x) for x in sorted(res, key=lambda x: (-len(x), x)) if res[x]]

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

题目大意：

求公交路线中最小换站次数

解题思路：

最值题且涉及到图，容易想到BFS。但此题难点在于不能将每个站作为一个节点，这样代码复杂且TLE。优化的做法是将路线作为节点，因为同一路线换站次数是一样的。属于一组节点作为一层的BFS。

解题步骤：

N/A

注意事项：

1. 将整条路线作为图的节点。这些节点都位于同一层，换乘不同路线才会换到下一层，路径+1
2. source和target所在的路线可能是多个，所以要将target所在的所有路线放在set中
3. 邻接表计算是用两条路线是否有交集，有交集才能换乘，才能进入下一层访问，Python用set(a) & set(b)
4. 如果target和source相等，返回0 (相等test case)
5. 站点不存在或者不存在任何路线，就返回-1

Python代码：

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

def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
	if target == source: # remember
		return 0
	graph = collections.defaultdict(list) # both set or list are fine
	queue, targets, visited, distance = collections.deque(), set(), set(), collections.defaultdict(int)
	for i in range(len(routes)):
		if source in set(routes[i]):
			queue.append(i)
			visited.add(i)
			distance[i] = 1
		if target in set(routes[i]):
			targets.add(i)
		for j in range(i + 1, len(routes)):
			if set(routes[i]) & set(routes[j]):
				graph[i].append(j)
				graph[j].append(i)

	while queue:
		node = queue.popleft()
		if node in targets:
			return distance[node]
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1
	return -1 # remember

TLE版本用station作为节点

Python代码：

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

def numBusesToDestination2(self, routes: List[List[int]], source: int, target: int) -> int:
	if target == source: # remember
		return 0
	graph, station_to_route = collections.defaultdict(list), collections.defaultdict(set)
	for j in range(len(routes)):
		r = routes[j] + [routes[j][0]]
		for i in range(1, len(r)):
			# graph[r[i - 1]].append(r[i])
			station_to_route[r[i]].add(j)

	queue = collections.deque()
	visited = set()
	bus_num = collections.defaultdict(int)  # remember collections.defaultdict(lambda: 1)
	for j in station_to_route[source]:
		for i in routes[j]:
			if i in visited:
				continue
			queue.append(i)
			visited.add(i)
			bus_num[i] = 1

	while queue:
		node = queue.popleft()
		if node == target:
			return bus_num[node]
		for j in station_to_route[node]:
			for i in routes[j]:
				if i in visited:
					continue
				queue.append(i)
				visited.add(i)
				bus_num[i] = bus_num[node] + 1
	return -1 # remember

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2), n = num of routes

题目大意：

长URL变成短URL方便传输和阅读，特别是很多社交网站对字数有限制如Twitter。

解题步骤：

解题思路：

1. 沟通清楚需要，用户数（都会很大）
2. 数据量估计。如火车售票系统，估计西雅图总人口，高峰乘坐人数。
3. 先完成一个功能。如buy ticket。画图，每个部件high level细节包括数据库的schema和组件间的API接口。
4. 自觉加上优化，如cache，master-slave数据库,LB等等。不要等面试官提醒
5. 完成一个功能后，再画图扩展到其他功能。

短网址长度：

短网址若只含数字，也就是十进制整数还是不够短。可以考虑加入大小写字母，总共有26x2+10=62，也就是一个62进制数。
网站总数是45亿个，62^7就远远大于45亿，7位就够。
若long表示的64位整数，log62(2^64-1)=11，大约是对应11位。

存储方法：

写操作：长网址到短网址
读操作：短网址到长网址
读操作远远大于写操作，所以key（或primary key）选在短网址， value在长网址。
每个新的长网址，对应一个短网址还是多个？考虑一下几点：

1. 若对应一个短网址，必须再产生一个unique key在长网址上来决定该长网址对应的短网址是否存在。大大降低写操作速度。
2. 长网址虽然一样，但可以带不同的header, user agent，从而知道进入该长网址的入口（其他网站），短网址商的盈利来源。
   所以长网址对应多个短网址，Google Maps就采取这个设计。

数据库选择可以是关系型数据库SQL Server，或者KV数据库如Redis，dynamoDB。可以详细讨论关系型数据库与No SQL的区别。
此题目用No sql比较好，因为从分布性考虑和是否需要复杂的Join操作来考虑，No sql有明显优势。

计算短网址：

另一个核心问题就是如何计算短网址，具体而言是怎么从URL转化为一个十进制整数。有几个方案：

1. 最简单的是维护一个最大值，每个新的请求，对此值加1。缺点是分布式系统中，维护单一最大值（所有机器中）大大降低性能。
2. 取URL的hash值得到64位整数再取前7位，但会有冲突。
3. 参考分布式发号器

十进制到62进制用短除法来做，

796%62=52， (796-52)/62=12.
12%62=12, (12-12)/62=0.
结果为(12)(52) = cP

DDOS：

这是一个细节考虑，若黑客大量发请求，耗尽所有ID怎么办？

1. 限制IP单日请求总数，超过直接拒绝。
2. 限制长网址的单一性。限制IP还不够，因为用proxy provider服务可以绕过这个限制。用Redis来cache长网址到短网址的一日数据，
   然后LRU淘汰旧的数据。这样如果此URL的请求超过一定数量，比如100次，就返回最新的短网址。
   长网址->次数+短URL

301还是302：

301是永久重定向，302是临时重定向。如果用了301， Google，百度等搜索引擎，搜索的时候会直接展示真实地址，那我们就无法统计
到短地址被点击的次数了，也无法收集用户的Cookie, User Agent等信息。这是短网址商的盈利来源。

Ref：

https://soulmachine.gitbooks.io/system-design/content/cn/tinyurl.html
https://segmentfault.com/a/1190000006140476

LeetCode 253 Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

题目大意：

输入[[0, 30],[5, 10],[15, 20]]表示每个会议的开始结束时间，求最少需要多少会议室能够安排所有的会议。

最小堆解题思路：

基于merging interval题目，首先按start排序。并且merge条件是start小于上一个会议的end。

1. 写几个例子感受一下。
   
   有两个重叠的会议，现在插入新的会议。是否再需要一个会议室取决于该新会议的开始时间小于这两个目前会议的终止时间的最小值。
   所以思路是用End time min-heap维护目前会议End time。若新会议start time小于堆顶元素，入栈且activeMeeting++，否则循环地出栈且activeMeeting–直到
   start time小于堆顶。
   这过程activeMeeting的最大值即所求。
   最坏情况是所有会议都重叠，复杂度为n* 2logn因为n个元素入堆出堆各一次，所以复杂度为nlogn，但会议一般不会集中，平均情况比排序法稍优。

注意事项：

1. Heap为结束时间的heap。
2. 类似于递减栈模板，用开始时间与堆顶的结束时间比较（表示这些会议均已结束），若大于堆顶，连续出堆。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
	intervals.sort()
	heap = [] # heap for end time
	max = 0
	for i in range(len(intervals)):
		# start time of the new meeting is earlier than on-going endtime
		while heap and intervals[i][0] >= heap[0]:
			heappop(heap)
		heappush(heap, (intervals[i][1]))
		if len(heap) > max:
			max = len(heap)
	return max

算法分析：

由于输入无序，所以先要排序O(nlogn), 而循环复杂度为O(nlogk), 所以总时间复杂度为O(nlogn)，空间复杂度O(k), k为所求也就是需要的会议室数。

排序法解题思路(推荐)：

1. 证明解与具体间隔无关，只与end time的值有关。
   
2. 基于1和2，对end time进行排序，题解只与start-end的相对顺序有关。既然这样，我们可以把所有start，end一起排序，也就是按时间轴排列，排成一个2n大小的数组，
   遇到start，activeMeeting++，遇到end，activeMeeting–。 这过程activeMeeting的最大值即所求。
   当然，上述方法直观，但实现起来需要建立一个class Node{value, startOrEnd}。本质上等价于对排序后的start数组和排序后的end数组进行合并排序。
   合并排序的结果等价于时间轴上两个数组的统一排序。当然，不需要剩余部分的合并排序，因为这部分不会增加activeMeeting的值。

解题步骤：

1. 排序start
2. 排序end
3. 合并排序，start小就activeMeeting++，否则activeMeeting–。求activeMeeting的最大值。

注意事项：

1. 若endpoint值相同情况下，要确保第二个排序先结束点，再出发点，因为相同点不算有重复飞机

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
	start = [(i[0], 1) for i in intervals]
	ends = [(i[1], -1) for i in intervals]
	endpoints = start + ends
	endpoints.sort()
	active_meetings, max = 0, 0
	for i in range(len(endpoints)):
		if endpoints[i][1] == 1:
			active_meetings += 1
		else:
			active_meetings -= 1
		if active_meetings > max:
			max = active_meetings
	return max

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)。