在职跳槽刷题打卡及适时分享感悟--计划明年2月面试

目前已经做了107题，用Python写，刷题计划是先按照frequency刷200+，对高频题和自己知识水平有个整体认知，然后根据自己情况按专题（pattern）来刷

10.28
今日打卡 994 （Medium)  1396 (Medium）215 （Medium）
994 是要多个node同步BFS 让我联想到 tree的 level by level traversal
215 做了heap的solution 很直接简单，但是interview的时候有的面试官可能会想考察 quik select的方法， memory usage是constant

10.30.2020

126. Word Ladder II （Hard）
今天至少花了6个小时在这个题目上，早晨起来先信誓旦旦地写个BFS solution，不是bug就是TLE，都有种绝望的感觉了。。。
不想直接抄答案，就看了点hint，看似是要通过BFS来找ladder length，然后再通过DFS去找paths，费了半天劲写完后发现还是TLE。。。
最后在youtube找了一个这个题目的解析视频，讲解得非常清晰👍
youtube 的video ID是 mIZJIuMpI2M
channel 名字是 TECH DOSE

视频里解法是先通过BFS来构建一个DAG (adjacency list ，对一个node，每个neighbor是child，有点topological sort的意思），然后再通过DFS + backtrack 来找到所有Path。在做BFS时，比较特别的是要用个rank map来track 每个node与beginWord的距离。

原来上算法课的时候，感觉自己对graph问题就一知半解，最近做了些BFS和DFS的基础题之后，以为对graph相关问题自己还是挺有把握的。这个Word Ladder 2真是让我原形毕露了。

说到底，自己的graph基础不足，复杂的问题也由一些基础的小问题组成的。列几个问题让自己去思考：
1. 给一个graph， 找node A 到 node B的所有最短路径？directed graph 和 undirected graph有没有区别？DAG 和非DAG中有没有区别？
2. 给一个graph， 找node A 到 node B的所有路径？
3. 如何判断graph中是否有Cycle？DAG 和 非DAG 有什么区别？

11.8

300. Longest Increasing Subsequence. (Medium)
用1dim DP的方法来做，对于每一个新的index i，需要check所有小于i的index，所以run time 需要O（n^2)
看到答案有一种更好解法是DP + binary search，
dp array "tails" storing the smallest tail of all increasing subsequences with length i+1 in tails
"We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update."
这样优化后，run time 变成了 O(n logn)


1428. Leftmost Column with at Least a One (Medium)
拿到这道题，先相想出的解法是每个row做bianry search，找出最左边的1的col index，然后再从所有row 中去最小的 col index
time complexity 是 O( (log n) * m)

后来看到答案有一个O（m+n）的解法，从matrix的top right开始寻找01的边际，碰到0向下，碰到1向右，最终current_col + 1就是要找column index，没有1的matrix是个special case要小处理一下，  这是最优解了。

1197. Minimum Knight Moves （Medium）
开始写了BFS的level by level traversal 会有TLE
后来加了visited set来避免重复visit，勉强过了AC
在答案中看到了DFS的解法，简洁又快速, knight 有8个方向的走法，但都是对称的，DFS解法中现将x y取了绝对值, 从（x，y ) 往回move， 只有两种move  (x -1, y -2) and (x-2, y-1), 因为取了绝对值 base case 有点tricky 会有这几个点 (0,0) , （1,1),  (2,0), (0,2), 后三点需要跨越quadrant 而且base moves 数是2
这道题的time complexity是多少？我还有点疑问

68. Text Justification (Hard)
这道题想法不难，关键在于如何写对和写的clean，这题我做得还行，一次过得AC，值得坚持的地方那个在于自己写完后，心理run了几个test case，找出了bug
下面这个代码，从别的答案看到的，值得借鉴，不我最开始写的while loop 简洁得多了

1.                     for j in range(space_total):
   
2.                         row[j % (len(row) -1)] += " "

复制代码

127 Word Ladder
上一次做这道题是两年以前了，没想到这次还是犯了和之前同样的错误，读完题了就默认是一个普通的BFS问题，先构建graph再写BFS，快速写完后submit，得到了TLE。。。这道题特殊的地方在于，graph其实已经无形中构造好了， 因为只有26个字母，可以通过穷举来寻找graph node的neighbors，这样一来在给定worldList 很长的时候， 就不用花时间去构造graph了
最后这题的runtime是O(N*26）

晚上又根据答案，implement了另一种解法，同过wildcard作为intermediate word，来构建graph， 比如word “dot”对应着 “_ot”、 “d_t”、 “do_” 3个word，每一个wild card word是graph的node，当两个original word 共享同一wildcard word的时候，他们之间就有edge了。 这个解法写起来更简洁，Time complexity O(M^2 * N), M is the length of each word in the word list, N是 size of word list

6 Zigzag Conversion
这个也是老题了，但是第一次写还是没AC，有个base case，rowNumber 是 1的时候，直接return string 就好,  这题的关键点在于如何swap traverse direction，我用的是boolean flag，后来看到高票答案中用了+1和-1的交替，写起来更顺

199. Binary Tree Right Side View
这道题乍一看，觉得好简单，以为直接沿着右边traverse就行。。。写到一半就发现不对了，left subtree 可以长于right subtree。后来想到了level by level traversal of Tree，通过两个Queue 来做，一个leve结束后，新Queue替换就Queue。 这种traversal还可以写通过每个level traverse完加null来做，答案有列，我自己写起来有些吃力，traverse之前需要有个start node。官方答案中还列了一个 DFS recursive 解法，我觉得挺巧妙的，通过 result list的length 来track level的层数

297. Serialize and Deserialize Binary Tree
一道经典题，感觉经常会被考到，几年前做的时候感觉很痛苦，今天看到题目想了想，AC一次过了。我之前解这道题的痛点在于不知道如何更好的处理null，总觉得需要一个符号来singal subtree的deserialization 结束了，用了一个queue之后，加上遇到”null”就终止的 deserialize的 if statement， 是可以通过recursion来自动deserialize的。感觉Tree 问题用recursion，容易想，也容易写。

10.31

152. Maximum Product Subarray
1-dim DP 问题，自己开始还比较担心 positve 和negative的情况，发现这样是分不清的，同过 curr_max_product, curry_min_product 和 nums[I] 来track max_product就行


234. Palindrome Linked List
这题涉及到两个小问题的组合，先要通过slow fast pointer 来找到list的 mid point， 然后再reverse list 从 next node of mid point 开始。最后从head 和 tail 分别 traverse，每步compare node value。
slow fast pointer 启示条件是 slow = head ， fast= head.next.next

没做其他coding题，好好学习了一下Design Twitter的系统设计题
列几个重点：
为了提高performance，每个User的timeline是precomputed ，存与redis cluster里面。
Precompute timeline 是通过 user 发tweet时，直接insert到user’s followers的timeline 里面，这个approach 叫做Fan-out
当一个user的followers的数量很大时，比如Justin Bieber，Fan-out将不会进行，直接从tweet table里Pull，所以最终的方案是mixed approach

11.1

139. Word Break (Medium)
开始写了一个recursion的解法，没有思考complexity，直接TLE了，然后想到可以用DP来做，对于index i ， iterate over word list 检查是否有word可以s[i - len(word)+1: i+1] == word and memo[i - len(word) ] = True

76. Minimum Window Substring (Hard)
今天花了很多时间做这题到AC，之前做了一些sliding window的题，这道题也可以同样的路子，不过update window的条件有点tricky，需要用counter来track character count，后来也看了下高票答案，比我解法要简单不少，有空再研究下

lz我这有打卡群和tc讲题群 可以考虑来我们这讲题

sanmao0715 发表于 2020-11-2 23:03
lz我这有打卡群和tc讲题群 可以考虑来我们这讲题

谢谢邀请，感觉自己时间太紧了，目前还是比较适合一个人复习，如果有问题想讨论话，欢迎在留言，我用空会回复的。

11.2

今天只成功做了一道题。。。
443. String Compression （Medium)
有点类似sliding window，right pointer 来sweep，left pointer 来写结果

767. Reorganize String 没想出来 明天再试试
1152. Analyze User Website Visit Pattern 题目需要进一步clarification 打算先放放 LeetCode官方估计会改进

今天花时间跟着Andrew Ng的video 重新学习了backpropagation的公式，感觉还挺有收获的，在backpropagate的过程中，每一层参数的求导是受下一层的结果影响的。

11.3
767. Reorganize String (Medium)
这题花了点时间，最后用heap做出来了，关键在于每写一个character，先用count最多的，最多的跟上一个重复，就用第二多的

547. Friend Circles （Medium)
这道题有点像number of islands，有DFS去找connected component

14. Longest Common Prefix （Easy)
需要用一个word来increase index

还尝试了420 Strong Password Checker，想出了一个方案，但总是过不了AC，理解了这道题为啥只有13%的AC， 明天再看看吧

11.4

13 Roman to Integer (Easy)
这题考察的是观察力，找到pattern，写出来很straight forward

今天只做了1道题，晚上突然不舒服，躺了几个小时才好些，刷题时间就没了，刷题之路慢慢呀。。。