KK's blog

每天积累多一些

0%

Design Chime

Posted on Edited on Disqus:

题目大意：

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<User> users = s.getUsers(); }

扩展问题：

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