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

11月21日
Leetcode
127. Word Ladder
127. Word Ladder II
41. First Missing Positive
88. Merge Sorted Array
160. Intersection of Two Linked Lists
System Design: How to design User System
接着上次的Friendship Service, 这个service最主要难点是如何存储friendship的数据，如果使用SQL, 可以把好友关系只存取一份，但是查询的时候需要查询两次，因为不确定哪一边是target id. 方法二是把好友关系存两份，查询只需一次。 如果使用NoSql,比如Cassandra, row key为user id, column key 为friend id.  在此我们分析一下数据库的优化: 对于Sql,我们可以使用index来加速查询操作,之所以速度提升是因为从以前的全表搜索变成了字段值单独提出来建立二叉树搜索。但是缺点是建立索引也需要占用空间,索引不能过多,否则在数据添加更新删除的时候会消耗更多时间,因为需要找到特定的位置以及保证有序，而不是像以前那样直接做修改。NoSql很容易horizontally scale, 通过对row key的consistent hashing即很容易实现sharding. 而Sql更容易实现vertical sharding.  对于选择NoSql还是Sql,主要取决几个方面: 1. 如果是有transaction,推荐使用Sql 2.如果data is structured and unchanging,推荐使用Sql. 3.如果想要repid development,意味着data structure经常变动,使用NoSql. 4.如果想要节省服务器资源而提高性能,选择NoSql, 也更容易scale across multiple data center.

11月22日
Leetcode
170. Two Sum III - Data structure design
545. Boundary of Binary Tree
229. Majority Element II
83. Remove Duplicates from Sorted List
355. Design Twitter
System Design:
复习News Feed 以及 看OOD设计 how to design Elevator, 主要用到strategy design pattern.

11月23日
Leetcode： 感觉对binary search的题边界情况还是把握不准，今天学习了地里的总结帖并专门训练了相关题目。
136. Single Number
268. Missing Number
Lintcode: sort colors II
852. Peak Index in a Mountain Array
367. Valid Perfect Square
374. Guess Number Higher or Lower
35. Search Insert Position
System Design: 今天看的还是OOD
How to design parking system: 需要以parking lot为视角进行操作, 然后主体主要有两个，vehicle和parking spot. 如果以最简单的logic来分析, parking lot里有list of spots. 每辆车会占用一个spot, 开出去会使得一个spot available. Vehichle也可能分为car, bus, truck等，spot也可能分多种。像这种管理类问题，如果两个对象主体之间产生操作关系，最好的易于扩展的方式是添加一个新的主体，比如receipt或ticket来处理vehicle和spot的关系，并可以记录停车时间和价格等信息。同理，记录租书, 吃饭, 预定等都适用。parking system只需要去控制ticket就可以完成对vehicle和spot的调控。

11月24日
Leetcode: 今天和小伙伴mock了几道easy和median的题，但是有很多个follow up,最后都涉及到大数据的处理，感觉效果比上次mock好多了。
349. Intersection of Two Arrays
350. Intersection of Two Arrays II
744. Find Smallest Letter Greater Than Target
441. Arranging Coins
662. Maximum Width of Binary Tree
System Design: OOD继续，how to design Black Jack?
主题从player角度出发，core object有hand, board, deck, suit等，use cases有Initialization, Play, Checkout, Shuffle(喜欢考算法)。

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

楼主早上起来刷两题，是要提前两小时起床么？

usagi21 发表于 2018-11-25 16:30
楼主早上起来刷两题，是要提前两小时起床么？

这个看情况吧，一般是早起一个多小时

11月25日
今天刷的是Lintcode 天梯，都是做过的题。
Lintcode
828. Word Pattern
488. Happy Number
451. Swap Nodes in Pairs
423. Valid Parentheses
389. Valid Sudoku
415. Valid Palindrome
System Design: 今天主要看了Uber tech blog, 讲了整体业务和架构方面的东西，把以前零碎掌握的东西顺了一遍。另外看了一些工作中要用到的一些前端的知识。

11月26日
Leetcode
78.Subsets
155.Min Stack
90. Subsets II
另外看了一些面经，脑海里过了一些算法题的解法
System Design: 看了另一个将messaging system的视频，有了新的角度，就是用redis来存用户最后的heartbeat的时间，用此来判断用户online还是offline。

Really nice post..

Good luck!

11月27日
Lintcode
7. Serialize and Deserialize Binary Tree
471. Top K Frequent Words
427. Generate Parentheses
640. One Edit Distance
902. Kth Smallest Element in a BST
927. Reverse Words in a String II
1001. Asteroid Collision
System Design: 今天又复习了一下rate limiter，因为听朋友说他已经在3+家公司问到这题了。温故而知新，这次又有了新的理解，主要是比较Token Bucket和Leaky Bucket的区别，Token Bucket是Guava Ratelimiter使用的也是此策略，即设定一个匀速投放token到bucket的速率，然后在infinite queue中等待的packet就可以acquire token。如果没packet来取token，则discard token。Leaky bucket是一个倒漏斗，口径小，packet只能匀速下落获取token，如果漏斗满了packet就会溢出，即丢失packet。这里还有一个主要不同，那就是token bucket能够应对突发流量，因为在bucket是满token的前提下能够迅速满足大量packet，这取决于bucket的size。而leaky bucket是强制的匀速获取。 如果有时间可以看下guava源码，它是可以像信用卡那样一次性预支，但是后面来的packet就要等待更久知道还债结束才能拿到新的token。这里需要用sliding window来解决前一秒和后一秒有大量request的情况发生。 第三种是用redis或者memached来hash按timestamp的分钟或者秒的粒度来统计counter，然后还需要设置失效时间，比如是限制一个小时为单位的request数量。那么一个小时后之前保存的记录删除，从而保证memory消耗量不高。保存格式为<key:user_id/ip , value: [timestamp1: counter1, timestamp2:counter2...]>或者<key:user_uniq_identify/timestamp , counter>.