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

转眼已经毕业两年了，也就是说已经有两年工作经验了，待在养老公司耗不起，断断续续刷了200多LeetCode，最近也开始陆陆续续约了一些公司的电面和onsite. 但是感觉System design的比重越来越大，在准备system design 的同时，刷题还不能落下。最近因为准备某家onsite的各种design，松懈了两周没怎么刷题，结果现在刷题的状态又没有了，就是那种给一道题能在几分钟内就有思路的状态。工作上又开始了新项目，各种新东西要学，真心感觉时间不够用。

决定还是来这里更新每天的目标和完成情况，让大家来监督我。

计划是
LeetCode : 每天刷题5道，除了一些easy题值得回味外，主要还是刷medium和hard.
System design: 虽然某些system design我已经看完一遍，部分看了两遍。但是感觉理解不够深入。所以决定每天深入一道设计题。记录并想明白各个feature和tradeoff.
当然最重要的还是需要不断总结和深入思考，不能只追求数量。


补充内容 (2021-07-06 14:54 +08:00):
最近跳槽了，有想回国的同学可以找我，通道：https://www.1point3acres.com/bbs/thread-776424-1-1.html

结合我最近看design的资料，给楼主一点建议吧。

1 着重在thinking process，不要想45分钟给一个完美的解决方案
2 条理要清晰，有big picture，有data modeling，有data flow
3 多从customer角度来考虑，用户要什么知道了，你才好决定你的设计中的取舍
4 不要一开始就挖大坑，从MVP开始，最后时间足够才加新的feature
5 从最开始简单的架构开始迭代，分析负载上去了之后的bottle neck在哪儿，你要怎么优化。这时候再带入一点customer最关心的是哪里，可以做哪些tradeoff。你做这个技术选型的原因是什么，因为技术mature还是没有spof
6 最后一定要review一下系统的scalability，负载x10的话，你的架构是不是线性的加资源进去就好了？
7 架构确定好了之后，最好来个预估要达到这个性能指标，我们需要多少机器以及怎么部署
8 别忘了提一嘴logging monitoring
9 扯一扯service oriented architecture也是极好的
10 把qconf 2012里scaling Pinterest from 0 to billions看几遍，我看了那么多资料里面，最有启发的一篇

总的来说，我不太建议一上去就摆一个高大上的架构，从小到大循序渐进的来，你就可以展现你更多的能力，不光有breadth还有depth。系统设计都是相通的，碰到没见过没准备的不要蒙蔽，毕竟要考察的是思维过程，不是要求你设计一个完美解决方案。

以上都是我的一家之言！

给楼主加个油 这样的功底 这样的毅力 大offer就在眼前

11月16日
Leetcode
722. Remove Comments
54. Spiral Matrix
59. Spiral Matrix II
118. Pascal's Triangle
119. Pascal's Triangle II
System Design:
How to design Uber: 今天白板了一遍Design Uber, 其workflow为Driver ->report their location every 4s -> Dispatch service -> update location information with 4,5,6 length of Geohash in Location Table(Redis) -> check if there is assigned trip id in Driver Table -> Retrieve Trip information from Trip Table in Dispatch Server -> Driver Accept/Deny/Cancel trip -> Update status in Trip Table in Dispatch Server and Driver Table in Geo Server -> Returned matched user to driver and matched driver to user.  这里User Table 和 Trip Table (trip_id, driver_id, user_id, latitude, longitude, status, created_at) 在Dispatch Server 里为SQL, Location Table (key: geohash, value: set of driver_id) 和 Driver Table(driver_id, lati, longi, status, trip_id, updated_at)为NoSQL使用Redis或者Cassandra.    使用NoSql是因为写操作要求更多，需要不断更新location.

祝你好运。你System design怎么刷的？

Laojiang 发表于 2018-11-7 04:55
祝你好运。你System design怎么刷的？

基本就是看完一个设计的视频，就跟着逻辑白板走一遍全过程，然后有遗漏的地方再过一遍

祝你好运，求视频推荐

11月6号：
Leetcode: 刷了关于interval的各种变形，发现这类问题很多公司都爱考，这类题目有很多，一天刷不完，明天继续.
目前理解是一种是需要维护一个list，先按start time排序，然后根据情况看是否需要再按end time排序. 然后依次遍历相邻时间片的首尾是否有overlapping.
第二是因为按照时间排序的有序数组，查找操作可以使用二分法，边界情况需要根据检查start time 还是end time来区别，大多是查找刚好overlapping的第一个点的位置
第三是可以利用TreeMap这个数据结构来简化操作，主要可以用在检查是否有overlapping和插入新的interval。对于合并和删除interval会比较复杂。
56. Merge Intervals(四刷)
57. Insert Intervals
435. Non-overlapping Intervals
729. My Calendar I
252.Meeting rooms
253.Meeting rooms II(四刷)
715.Range module
System Design: Design Tiny URL
主要有两种方法生成shortened url, 一种是encode actual URL,即对原url进行自增ID进行进制转换或者随机生成的方式生成一个短url，去查询有没有duplicate，直到生成一个unique的key. 另一种推荐的方式是把所有随机生成好的6位的key全部放入key-Database中，（只所以是6位是因为通过Base62可以得到62^6=57billion个url）然后每次来一个url，我们先检查是否已经存在过，没有的话直接从DB中拿出一个直接赋给它即可。 DB使用NoSql,因为没有复杂的relationship和query，也没有transaction. 性能提升使用cache，跨地区使用不同的DB，cahce和server. Scale out DB的策略可以使用对key进行hashing 然后使用consistent hashing进行分配.

11月7号：
Leetcode: 其实Skyline问题也是interval的一种，只不过从一维变二维，求的是overlap的最高位。其他变形也可以是求overlap的最低位，此类问题需要多思考，变形非常多。
731. My Calendar II
759. Employee Free Time
807. Max Increase to Keep City Skyline
218. The Skyline Problem
11.Container With Most Water
System Design: 白板走了一遍Tiny URL, 并过了一遍输入url,浏览器端会发生什么的整个过程，URL->DNS resolution (IP lookup from browser, OS , router, DNS cache first, DNS query later form Domain) -> Server with TCP connection-> HTTP request -> Waiting for response -> server send request to application -> code execution and DB query -> response -> transferring data -> CDN (css, js, image, video ) -> browser presenting.

weixue 发表于 2018-11-7 12:00
祝你好运，求视频推荐

不知道为什么回复没被管理员通过，主要视频还是地里推荐的那些

11月8号
Leetcode:
200. Number of Islands
336. Palindrome Pairs
163. Missing Ranges
694. Number of Distinct Islands
736. Parse Lisp Expression
System Design: Design Logging System, 这题感觉更像是OOD, 使用Observer Pattern Design或者Aspect Oriented Programming的方式去做logging。

11月9号
LeetCode:
416. Partition Equal Subset Sum
698. Partition to K Equal Sum Subsets
701. Insert into a Binary Search Tree
450. Delete Node in a BST
161. One Edit Distance
System Design: Design Typehead
此题的场景是搜索框，每输入一个单词，就会给出top k的单词推荐，这些推荐是根据用户对这些单词的点击率，需要使用Trie来解决。所以我们需要两个service，一个是DataCollectionService和QueryService, DataCollectionService会定时从Log DB中统计每个词的点击次数，然后offline跟新QueryService中Trie, 为了保证速度，Trie存入In memory中，但是为了不会是Trie丢失，还需要在disk中存一份Serialized trie. 当Trie过大无法存入一个In memory的Cache中时，我们需要多台机器，以每个prefix做consistent hashing的key来存入不同的机器中而不是以每个单词的首字母来把所有prefix存入,这样还是存在一个机器存不下，而使得同一个prefix的所有top word存入不同机器中。另一个优化是，在浏览器端使用cache,一个是cache已经输入过的prefix，当重复删去和添加相同的prefix时可以避免request from server, 还有一个优化是每输入一个prefix，就多加一个单词在前端存储下一个prefix的前1000个word.