KK's blog

常用知识点

1
2
3
4
5
6
7
8

PriorityQueue<Node> minHeap = new PriorityQueue<Node>(k,
				new Comparator<Node>() {
					@Override
					public int compare(Node o1, Node o2) {
						return o1.value - o2.value;
					}
				}
		);

Arrays的二分法： 若找不到，返回比tgt大的数的下标数组长度的负值-1。

1
2
3
4
5
6
7
8

int[] lis = new int[len];
int index = Arrays.binarySearch(lis, 0, len, tgt);
if(index < 0) {
	index = -index - 1;
	lis[index] = tgt;
}
else
	lis[index] = tgt;

题目大意：

生成唯一ID如用户ID，订单ID。

解题思路：

基本思路是将所有网站映射到一个整数。
三大核心需求：

1. 全局唯一(unique)
2. 按照时间粗略有序(sortable by time)。按时间查询是普遍的请求，如得到最新的1000个用户。
3. 尽可能短。省空间，查询要更有效率。

UUID：

UUID是一类算法的统称，具体有不同的实现。UUID的有点是每台机器可以独立产生ID，理论上保证
不会重复，所以天然是分布式的，缺点是生成的ID太长，不仅占用内存，而且索引查询效率低。
4个字节表示的Unix timestamp,
3个字节表示的机器的ID
2个字节表示的进程ID
3个字节表示的计数器

多机器分别自增：

假设用8台MySQL服务器协同工作，第一台MySQL初始值是1，每次自增8，第二台MySQL初始值是2，
每次自增8，依次类推。前面用一个 round-robin load balancer 挡着，每来一个请求，由
round-robin balancer 随机地将请求发给8台MySQL中的任意一个，然后返回一个ID。
load balance可以确保请求平均分配到不同的机器，所以粗略有序，缺点是加机器要re-hash这些Id
且顺序不够稳定。

Twitter Snowflake：

原理与UUID基本一样。也是时间戳+机器id+自增序号。时间戳保证有序。

题目大意：

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
73
74

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攻击

LeetCode 019 Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

题目大意：

删除一个单链表末尾开始算起的第n个结点，然后返回该单链表。 例如：
输入: 1->2->3->4->5 其中n=2；
输出： 1->2->3->5;
n一定合法，只能遍历一次链表。

解题思路：

这是经典题。两指针法。距离为N的两指针，当前指针到末尾，后指针即是要删除的节点。头部插入fake节点，类似于mergeIntervals L56末尾插入一个空节点避免特别化处理。

1. 快指针从fake节点开始先走n步
2. 慢指针开始一起和快指针同步走，直到快指针到最后一个（next为空）
3. 此时慢指针是要删除指针的上一个，删除操作是可以的。

注意事项：

因为头指针也可能被删除，如只有一个节点的链表，n=1。删除操作在待删除节点的上一个节点上操作，所以引入假头节点prehead。

Java代码：

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

public ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode prehead = new ListNode(-1);
	prehead.next = head;
	
	ListNode slow = prehead, fast = prehead;
	for(int i=0;i<n;i++)
		fast = fast.next;
	
	while(fast.next != null){
		fast = fast.next;
		slow = slow.next;
	}
	deleteNode(slow);
	return prehead.next;
}

public void deleteNode(ListNode p){
	p.next = p.next.next;
}

算法分析：

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

LeetCode 658 Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10⁴
3. Absolute value of elements in the array and x will not exceed 10⁴

题目大意：

给定一个排序数组，两个整数k和x，求数组中距离x最近的k个数字。结果应该有序，距离相同时优先选择较小的数字。

解题思路：

1. 进阶二分法找出第一个大于等于key值的元素。
2. 左右两指针搜索k个元素。

注意事项：

1. 指针不能越界
2. 根据题意，与key距离一样时，取较小元素。

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

public List<Integer> findClosestElements(int[] arr, int k, int x) {
	int upperIdx = firstEqualOrGreater(arr, x);
	int lowerIdx = upperIdx-1;
	List result = new ArrayList();
	for(int i=k;i>0;i--){
		if(lowerIdx<0)
			result.add(arr[upperIdx++]);
		else if(upperIdx>=arr.length)
			result.add(arr[lowerIdx--]);
		else if(x-arr[lowerIdx]<=arr[upperIdx]-x)
			result.add(arr[lowerIdx--]);
		else
			result.add(arr[upperIdx++]);
		
	}
	Collections.sort(result);
	return result;
}

public int firstEqualOrGreater(int[] a, int key){
	int lo = 0, hi = a.length-1;
	while(lo<=hi){
		int mid =  lo + (hi - lo) / 2;
		if(a[mid]<key)
			lo = mid+1;
		else
			hi = mid-1;
	}
	return lo;
}

算法分析：

时间复杂度为O(logn+k)，空间复杂度O(1)。