在职刷题 + System Design + 面试准备的路上

11月10号：
LeetCode:
436. Find Right Interval
150. Evaluate Reverse Polish Notation
33. Search in Rotated Sorted Array
383. Ransom Note
82. Remove Duplicates from Sorted List II
System Design:
今天主要在看design, 看了两个design，一个是Design Google sheet, 一个是Design messager.
Design Google sheet 的主要问题是用什么数据结构来存储ceil, 并进行增删改查的操作，并且需要用判断有向图是否带环(BFS or DFS)的算法来判断是否有circular dependency。 另外多人同时操作，使用的原理是Latency compensation是先写在page上，并predict这是最终显示结果，同时server端会去sync，是否有其他人也在修改，如果有的话则需要重新根据时间顺序来覆盖操作，如果无人修改则保留原有记录。server sync的原理是一个线程锁住log，并把此次的event加入log中，然后释放log. 保证所有thread读到的都是最新的log
Design messager 的主要feature就是发信息,群聊和在线状态检查。发消息的主要问题是如何使用合理的db存储和如何即时通信，存储DB要设计好合理的table,比如message和thread table, 而通信可以分为两个service,一个message service，一个push service. message service负责接收user的message，存储进db，并发送给push service，push service负责与user进行socket连接并发送message. 群聊需要在message 和push service中间加入channel service，这样channel service负责接收一次message service的message，然后发送给subscribe在channel service上的active user. message serveice 会帮忙subscribe，而push service会知道用户是否在线，下线的时候remove user from channel.  查在线状态通过user每4秒pull一次state of friends and tell server itself is alive.  这个方式和uber司机不断的告诉server自己的位置一样，也是heartbeat的方式来告知server是否在线。

11月11号
LeetCode
695. Max Area of Island
358. Rearrange String k Distance Apart
480. Sliding Window Median
69. Sqrt(x)
221. Maximal Square
System Design
Rate Limiter: 目前了解的有三种，第一种是token bucket, 意思是给每个user一个bucket，里面放了规定的k个token，同一分钟或者小时(根据要求)来的request，我们会给token直到数量为0. 第二种是leaky bucket, 就是给每个user分配一个buffer，规定buffer的容量，满了就不serve其他request，直到来的request的时间与buffer中的第一个相差时间超过一定数额，就pop出，再插入新的request。第三种是记录每一分钟或者秒有多少个request同时来，然后每来一个request，就判断当前时间的一分钟内有多少个request，少于k就serve并记录，可以用redis或者Memcached来实现。

请问楼主边上班边刷题时间都是怎么安排的？我也是在职刷题，感觉工作日能做个三四个新题脑子就已经不转了，还要看system design，时间精力都很不够用啊

Somehow 发表于 2018-11-13 00:22
请问楼主边上班边刷题时间都是怎么安排的？我也是在职刷题，感觉工作日能做个三四个新题脑子就已经不转了， ...

我坚持的也很痛苦，基本上是早上起来做两题，下午抽空做一题，晚上做剩下的和system design.  新题刷不动了就看旧题想思路。工作上肯定会有影响的没办法

guaitt 发表于 2018-11-13 12:53
我坚持的也很痛苦，基本上是早上起来做两题，下午抽空做一题，晚上做剩下的和system design.  新题刷不动 ...

谢谢楼主分享啊，也祝楼主早日找到心仪的工作～

11月12
LeetCode:
36. Valid Sudoku
37. Sudoku Solver
767. Reorganize String
741. Cherry Pickup
99. Recover Binary Search Tree
System Design
为了避免遗忘之前看过的，今天复习了一下Tiny URL 和 Rate Limiter.
Rate Limiter再复习的时候又有了新的理解，关于第三种方法Memcached虽然能够很好的handle分秒级别的粒度，但是对于小时和天，如果只记录每小时，很容易出现一个小时的最后1秒和下一小时的第1秒有大量request，所以对于较大粒度，我们需要一方面去aggregrate之前细粒度的数据变为相对粗粒度的数据，一方面需要保持最近细粒度数据以便能够处理临界情况。还有一个是如何限制30分钟或者1个小时不能再登录的问题，我们可以在数据库中新添一个column为next available time，标明解冻时间。

Lz自己过一遍design的方式觉得很好啊。。。能不能私信一下design的视频链接呢，谢谢哈

求视频地址

自己过一遍design的方式觉得很好，能私信一下design的视频链接吗？ 太谢谢了

同求链接，什么地方找到的系统设计的视频?  谢谢