KK's blog

LeetCode 128 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

**Input:** [100, 4, 200, 1, 3, 2]
**Output:** 4
**Explanation:** The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.

题目大意：

给出一个未排序的整数数组，找出最长的连续元素序列的长度。
如： 给出[100, 4, 200, 1, 3, 2]，最长的连续元素序列是[1, 2, 3, 4]。返回它的长度：4。

解题思路：

这是连通问题，如果用排序方法，很容易，但时间复杂度为O(nlogn)。考虑改进，因为连通集，容易想到HashMap，把每个元素加入到其中，
然后对每个元素进行相邻查找。相邻查找就是以此元素为中心，向上向下在Map查找，从而得到此元素的最大连续序列长度。查找过的元素
在Map中删除，以免重复计算。

注意事项：

1. 加入set之后的元素不能再内循环中删除，因为外循环是遍历每一个数，可能会遍历到删除的数，正确做法是用map的value来记录是否访问过。

Python代码：

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

def longestConsecutive(self, nums: List[int]) -> int:
	num_set = collections.Counter(nums)
	res = 0
	for n in nums:
		if num_set[n] == 0:
			continue
		max_len = 1
		num_set[n] = 0
		i = n + 1
		while i in num_set:
			num_set[i] = 0
			max_len += 1
			i += 1
		i = n - 1
		while i in num_set:
			num_set[i] = 0
			max_len += 1
			i -= 1
		res = max(res, max_len)
	return res

注意事项：

1. Java中在for循环中不能修改hashSet，所以只能用HashMap且value存boolean替代。HashMap表示此Map还是否含有该元素。

Java代码：

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

public int longestConsecutive(int[] nums) {
	int result = 0;
	HashMap<Integer,Boolean> hm = new HashMap<Integer,Boolean>();
	for(int i : nums)
		hm.put(i, true);
	
	Iterator it = hm.keySet().iterator();
	while(it.hasNext()){
		int key = (int)it.next();
		int i = key+1;
		int count = 1;
		while(hm.containsKey(i) && hm.get(i)){
			count++;
			hm.put(i, false);
			i++;
		}
		i = key-1;
		while(hm.containsKey(i) && hm.get(i)){
			count++;
			hm.put(i, false);
			i--;
		}
		if(count>result)
			result = count;
	}
	return result;
		
}

算法分析：

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

题目大意：

Design a chatting application like Chime

了解用户需求：

通过不断和面试官沟通，了解用户角度的需求。把这些需求逐一列举在白板上。面试者一开始会刻意只说出1-2点。面试者通过联系实际，不够构想
一些需求，若得到确认就要写入。

1. 用户可以单对单相互聊天(one-on-one chat)
2. 用户可以群聊(group chat)
3. 用户可登陆
4. 用户可以添加好友(sending)，接受好友(accepting)，拒绝添加(rejecting). 好友相互添加(mutual)，不支持两人分别添加。
5. 用户更新状态为offline, available, busy, don’t disturb，还有个性化签名

面试者通过重新排序user life cycle更有助于理解和记忆

1. 用户可登陆
2. 用户可以添加好友(sending)，接受好友(accepting)，拒绝添加(rejecting)
3. 用户可以单对单相互聊天(one-on-one chat)
4. 用户可以群聊(group chat)
5. 用户更新状态为offline, available, busy, don’t disturb，还有个性化签名

本面试不支持以下use cases
音频会议，视频会议，文件传输

Block/Component diagram：

最简单的设计就是一系列的clients，一系列的servers，还有存储系统。

存储系统可以选择SQL或者No SQL。No SQL就会更加scalable.这里可以讨论它们之间的pros和cons。
传输协议(client-server)可用Java中的Socket和ServerSocket对象，它们建立一个TCP连接，用IO Stream传输。
服务器端用多个服务器避免single point of failure。server端的memory会存一些用户状态等数据（当然它也会被持久化），这表示它需要
replicate一些数据减少不同机器之间的lookup时间。

这些大概讨论一下即可，本design主要针对OOD。

Class diagram：

从User开始写fields和key methods，因为需求就是针对用户，比较直观。当参数含有多个属性时，就应该考虑产生一个新的class，如Message，
因为Message不只内容String还有发送时间甚至styling等。 还有注意每个类是否存在状态(如UserStatus)，如果有，就要考虑用enum。

Java代码：

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

User:
   int id;
   String fullName;
   String alias;
   List<User> friends;
   List<GroupChat> gChats;
   List<PrivateChat> pChats;
   UserStatus s;
   
   void sign();
   void signout();
   void sendFriend(FriendRequest r);
   void acceptFriend(FriendRequest r);
   void rejectFriend(FriendRequest r);
   void setUserStatus(UserStatus s);
   PrivateChat createConversation(User b);
   GroupChat createConversation(List<User> c);
   void sendMessage(PrivateChat s, String msg);
   void sendMessage(GroupChat s, String msg);

Conversation:
   int id;
   List<User> users;
   List<Message> messages;
   
   void addMessage(Message msg);
   
PrivateChat extends Conversation:
   PrivateChat(User user, User user2);

GroupChat extends Conversation:
   void addUser(User u);
   void removeUser(User u);
   
Message:
   int id;
   Date timestamp;
   User user;//I would like to know who sent this msg
   String content;

FriendRequest:
   User from;
   User to;
   Date timestamp;
   RequestStatus Status;

UserStatus:
   String message;
   UserStatusType type;

enum RequestStatus:
   ACCEPTED, REJECTED, PENDING
 
enum UserStatusType:
   offline, available, busy, DONT_disturb

//这个类最为复杂，主要是维护用户关系和用户状态以及对应的数据库读写。这里有几个隐形需求。。可以根据alias搜索用户，  
//如果用户offline，即使是好友也不能发信息。它是singleton。
UserManager:
   HashMap<String, User> usersByAlias;
   //User类需要含有UserManager，查看要发送信息的对象是否在线，若不在线，不能发出信息。
   HashMap<Integer, User> onlineUsers;
   
   public static UserManager getInstance(){
       if (instance==null) instance = new UserManager();
	   return instance;
   }
   //用observer模式，User调用UserManager这个接口来更新onlineUsers
   void signInUser(String alias);
   void signOutUser(String alias);
   //User to的acceptFriend会调用这个函数来更新User a和User b的friend list同时更新FriendRequest的状态。
   void approveRequest(FriendRequest f);

具体实现可以选择approveRequest或者某用户发信息怎么令group chat的其他用户收到该信息sendMessage(GroupChat s, String msg)。

void sendMessage(GroupChat s, String msg){
List users = s.getUsers();
}

扩展问题：

1. 怎么知道某用户真的在线
2. 怎么处理内存和数据冲突的信息
3. 怎么让server scale
4. 怎么防止DDOS攻击

题目大意：

长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 273 Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ - 1.

Example 1:

**Input:** 123
**Output:** "One Hundred Twenty Three"

Example 2:

**Input:** 12345
**Output:** "Twelve Thousand Three Hundred Forty Five"

Example 3:

**Input:** 1234567
**Output:** "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

**Input:** 1234567891
**Output:** "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

题目大意：

这是将非负整数转化为其英文单词表示。给定输入确保小于 2 ^ 31 - 1

解题思路(推荐)：

第二种方法是按千位递归的。下面的方法是按20以下，100以下，百位，千位…递归，递归的颗粒度更小，程序更简单。

注意事项：

1. 在入口方法中，若num为0，则返回Zero，要单独列出。
2. 在递归中，num为0要单独列出，因为0表示此位不存在，可以记在dict中或返回空字符串。
3. strip来去掉空格。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

NUM_DICT = {
    0: '',
    1: 'One',
    2: 'Two',
    3: 'Three',
    4: 'Four',
    5: 'Five',
    6: 'Six',
    7: 'Seven',
    8: 'Eight',
    9: 'Nine',
    10: 'Ten',
    11: 'Eleven',
    12: 'Twelve',
    13: 'Thirteen',
    14: 'Fourteen',
    15: 'Fifteen',
    16: 'Sixteen',
    17: 'Seventeen',
    18: 'Eighteen',
    19: 'Nineteen',
    20: 'Twenty',
    30: 'Thirty',
    40: 'Forty',
    50: 'Fifty',
    60: 'Sixty',
    70: 'Seventy',
    80: 'Eighty',
    90: 'Ninety',
}
class Solution(TestCases):

    def numberToWords(self, num: int) -> str:
        if num == 0:
            return 'Zero'
        return self.dfs(num)

    def dfs(self, num: int) -> str:
        if num < 20:
            return NUM_DICT[num]
        elif num < 100:
            return (NUM_DICT[num // 10 * 10] + ' ' + self.dfs(num % 10)).strip()
        elif num < 1000:
            return (NUM_DICT[num // 100] + ' Hundred ' + self.dfs(num % 100)).strip()
        elif num < 1000000:
            return (self.dfs(num // 1000) + ' Thousand ' + self.dfs(num % 1000)).strip()
        elif num < 1000000000:
            return (self.dfs(num // 1000000) + ' Million ' + self.dfs(num % 1000000)).strip()
        elif num < 1000000000000:
            return (self.dfs(num // 1000000000) + ' Billion ' + self.dfs(num % 1000000000)).strip()
        return ''

注意事项：

1. 空格总加在新数前面，只需要加在有返回值的时候，也就是tens和lows中，其他如numberToWordsR(number/1000)
   可能返回空值，此时不在前面加空格。
2. 在递归中，num为0要单独列出，因为0表示此位不存在，也就是无返回值。
3. 在入口方法中，若num为0，则返回Zero，要单独列出。

Java代码：

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

public String numberToWords(int number) {
	if (number == 0)
		return "Zero";
	
	return numberToWordsR(number).trim();
}

public String numberToWordsR(int number) {
	if(number == 0) {
		return "";
	} else if (number < 20) {
		return " " + lows[number];
	} else if (number < 100) {
		return " " + tens[number / 10] + numberToWordsR(number % 10);
	} else if (number < 1000) {
		return " " + lows[number / 100] + " Hundred" + numberToWordsR(number % 100);
	} else if (number < 1000000) {
		return numberToWordsR(number / 1000) + " Thousand" + numberToWordsR(number % 1000);
	} else if (number < 1000000000) {
		return numberToWordsR(number / 1000000) + " Million" + numberToWordsR(number % 1000000);
	} else {
		return numberToWordsR(number / 1000000000) + " Billion" + numberToWordsR(number % 1000000000);
	}
}

算法II每三位解题思路：

这是logical and maintainable的经典题。按照英语的习惯，每三位是一组，所以实现的时候，也是按千为分组，有一个方法去处理一千
内的数。一千以内也分为三种情况，20以内，几十，其他。20以内和几十都是特殊情况的单词，所以可以放入数组或HashMap，数组比较
好，因为可以直接用索引读出。大于一千的数，可以用递归来做，从人的习惯，从低位到高位，每三位加一个逗号分隔。所以同样，算法
也是从低位开始，若千位内的数大于0，加入Thousand, Million等，每三位调用千位方法，再递归。
group的引入作为递归的层次来决定Thousand还是Million。
由于从低位递归，所以倒着做，要reverse地加入到结果，最终结果再reverse回来。

注意事项：

1. 空格总加在新数前面，也就是append前先加空格
2. 低3位大于0才加Thousand, Million等词，也就是低三位在1-999之间，若为0如1 million。

Java代码：

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

public String[] lows = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
   "Eleven", "Twelve","Thirteen", "Fourteen","Fifteen","Sixteen","Seventeen","Eighteen", "Nineteen"};

public String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

public String numberToWords(int number) {
	if(number == 0) {
		return "Zero";	
	}

	StringBuilder result = new StringBuilder();

	translateThreeR(number, result, 0);
	return result.reverse().toString().trim();
}

public void translateThreeR(int number, StringBuilder result, int group) {
	int lower = number % 1000;
	int thousands = number / 1000;     

	if (group == 1 && lower > 0)
		result.append(reverse(" Thousand"));
	else if (group==2 && lower > 0)
		result.append(reverse(" Million"));
	else if (group==3 && lower > 0)
		result.append(reverse(" Billion"));
	
	if(lower>0)
		result.append(reverse(translateThree(lower)));
	
	if(thousands >= 1) {
		translateThreeR(thousands, result, ++group);
	}

}

public String translateThree(int number) {
	StringBuilder result = new StringBuilder();
	if(number > 99) {
		result.append(" "+lows[number / 100]);
		result.append(" Hundred");
		number = number % 100;
	}

	if(number > 19) {
		result.append(" ");
		result.append(tens[number/10]);
		number = number % 10;
	}

	// Remainder is under 20
	result.append(" "+lows[number]);
	return " "+result.toString().trim();
}

public String reverse(String s) {
	return (new StringBuilder()).append(s).reverse().toString();
}

算法分析：

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

Follow-up：

integer, minus, decimals, internationlization(localization)。

LeetCode 493 Reverse Pairs

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Example 1:

**Input:** nums = [1,3,2,3,1]
**Output:** 2

Example 2:

**Input:** nums = [2,4,3,5,1]
**Output:** 3

Constraints:

• 1 <= nums.length <= 5 * 10<sup>4</sup>
• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

题目大意：

求数组的逆序数

解题思路：

1. Merge sort模板
2. merge分两部分写，一个部分比较求个数，另一部分排序

注意事项：

1. merge分两部分写，一个部分比较，另一部分排序
2. 计算个数由两部分组成，两指针部分和剩余元素部分。若以后半数组为主，就是前半数组指针i的后面个数(程序用此)
   若以前半数组为主(加入到res时候)，就是后半数组指针j的前面个数
3. nums[start:end+1] = res，前面是nums不是res

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

def reversePairs(self, nums: List[int]):
	if not nums:
		return 0
	return self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums, start, end):
	if start >= end:
		return 0
	mid = start + (end - start) // 2
	count = 0
	count += self.m_sort(nums, start, mid)
	count += self.m_sort(nums, mid + 1, end)
	count += self.merge(nums, start, mid, end)
	return count

def merge(self, nums, start, mid, end):
	i, j, res, count = start, mid + 1, [], 0
	while i <= mid and j <= end:
		if nums[i] <= 2 * nums[j]:
			i += 1
		else:
			count += mid - i + 1
			j += 1

	while i <= mid:
		i += 1
	while j <= end:
		count += mid - i + 1
		j += 1

	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1

	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1

	nums[start:end + 1] = res
	return count

算法分析：

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