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

2019年1月1号：新年新气象，相信每个人的努力都不会白费。
397. Integer Replacement: DFS or 根据n-1或n+1的1bit数来确定选择，1越少越快完成
333. Largest BST Subtree: check if BST and count or record size of BST and lower and upper boundary for each node, use PostOrder traversal compare the value of parent with upper of left and lower of right and update till to the top root.
543. Diameter of Binary Tree: Postorder traversal, bottom-up get heights of left and right side for each node and record max
572. Subtree of Another Tree: similar with isSameTree or serialize two trees and find substring.
面经题：
1. Collatz Conjecture : Memoization
2. Implement Queue with limited size of array : Store List<Object> in last position of List<Object>
System Design: Designing Pastebin
主要功能有保存一段文本并生成一个unique URL 读取。类似于TinyURL功能，多了一个文本生成和保存。content可以使用object storage like Amazon‘s S3保存。其他信息比如Paste 和 User信息用SQL存储. Paste包含URL, ContentKey, UserId, CreationData, Expiration.  URL的生成可以通过Key Generation Service. Generate random six letters strings beforehand and store them in DB. 可以 keep some keys in memory whenever a server needs them.  牢记80-20 rule, 20%的URL会产生80%的traffic。所以需要Cache这20%的paste.并可以此计算需要的space大小。

请问某章的视频在哪可以买啊  我问了他们说不卖视频

Thirty9 发表于 2019-1-3 03:17
请问某章的视频在哪可以买啊  我问了他们说不卖视频

他们没有视频但有课程啊

2019年1月2日
LeetCode 上班第一天精力不够用，只刷了一题.
251. Flatten 2D Vector: 1. Maintain two iterators. Iterator of list and iterator of integer.  2. Two pointers and list of list.
System Design: Design Instagram
本来以为Instagram会有什么不一样的Design，发现Grokking上讲的就是Design Twitter的略简单版本。主要功能有upload/download/view image/video, Newsfeed/Timeline, follow and unfollow friends.  首先是分析DAU，QPS. 然后是分析存储这些image/video需要多少空间，存储1年需要多少. 然后存储就可以使用file system like S3. 而Friendship 和 User, Photo 的metadata需要使用Sql存储. 然后是News feed 的两个mode，pull and push, 最佳策略是hybrid两个，对于所有人使用push，对于hot users with lots of followings 使用pull.  对于Scalability这块，我们需要根据photo id 来做metadata的sharding，原因是如果对于userID做sharding，会导致几个问题，一是对于hot users和一些拥有大量image/video的用户，通过userID来做partitioning可能一个shard并不能存储该user的全部信息，反而会影响性能。还有一个问题是把一个user的所有信息都放在一个shard的话，如果这个shard down了，那么他的所有信息都会unavailability。如果这个用户是hot users那么也可能产生high latency if it's serving high load.  对于photo的ID我们可以使用Key generation service提前生成，为了避免single point failure，我们可以使用两个DB，一个放odd incrementing number一个放even incrementing number. 每个photo只需要去take一个id即可，保证了the sequence of auto incrementing ID. Then use load balancer to deal with downtime.   对于实现快速获取最新的photo，可以使用photo ID用epoch time + incrementing number. 这样的好处是能够加速数据库的查找操作，因为我们肯定会index photoID.

1月3日
刷面经：
1.Display Page: use Iterator.
2.Travel Buddy
System Design: Design Dropbox
这个设计相关的知识点对我来说比较新，所以看完一遍能掌握的部分并不多。先来第一遍吧，主要的功能有upload/download files, share files/folders with other users, support automatic synchronization between devices, support offline editing.  Files 存储在file system中，Metadata of Chunks, files, User, Devices, workspace(folders)存储在SQL中。对于files的同步操作，比如update的主要的workflow为用户A上传chunks, 更新metadata并commit changes，A得到confirmation，并发送notification给B、C, BC接收到metadata changes并download updated chunks.  对于ABC同时更改同一个file，需要把他们更改的操作按时间顺序放入同一个request message queue中依次处理。然后分别创建response message queue给每一个client来响应。对于文件的上传，是把一整个file分为多个chunk来上传，为了节省空间避免duplicate，我们可以在上传前去hash chunks and lookup.如果发现已经含有，则only add the reference rather than the full copy.

1月4日
Leetcode: 今天按专题刷Union Find 和DFS是好朋友
482. License Key Formatting: Iterate over from end to beginning.
399. Evaluate Division: Union find or DFS
721. Accounts Merge: Union find or DFS
737. Sentence Similarity II: Union Find
959. Regions Cut By Slashes: DFS

加油。。。。

1月5日
Leetcode
811. Subdomain Visit Count
844. Backspace String Compare
843. Guess the Word
683. K Empty Slots
857. Minimum Cost to Hire K Workers

1月6日
LeetCode
336. Palindrome Pairs: HashMap or Trie Tree
面经
5.Travel Buddy: sort by similarity
6.File System

1月7日
Leetcode
771. Jewels and Stones
709. To Lower Case
734. Sentence Similarity
415. Add Strings
674. Longest Continuous Increasing Subsequence
面经：
Find Median in the large file of integers