For recursion, it’s too easy. 3 BT traversals using stack(iterative way to solve it).
- 就記得pre-order和in-order用幾乎百分之99一樣的模板, 差別是一個 root node first另外一個是left order first
- post-order最tricky, 就記得我們最後會reverse postorder, 所以root node就直接給他放進去postorder.
Code:
Usually, when it comes to combination problems, the most naive way to solve the problem is generate all possible solutions. And, we use depth-first-search(DFS) or called backtracking technique.
For backtracking, when we do time and space complexity analysis, they follow a certain pattern:
T: O(n**m), n raise to power of m, where n represents at most we have n branches can search for current state and m is maximum depth of recursion tree.
Note: O(n**m) will be upper bound of time complexity. For some cases, if we generate all possible combinations or partitions , given an integer or a string, running time will be O(2**n), lower than upper bound.
S:O(m), where m is maximum depth of recursion tree. (if we don’t consider space of storing answer)
- 39. Combination Sum
- 131. Palindrome Partitioning
- 291. Word Pattern II
Given 一個string expression, 我們要去計算result of expression.
有三個題型:
最基本的計算機題型
1.是string裡面只有+-(), 沒有乘除. (See LC 224)
2.再來是有+-*/但沒有() (See LC 227)
3.最難版本是+-*/和()都有(See LC 772)
Note:
- 上面這些題型都可以假設沒有leading negative integers. For example, “-3+2” or “(-3+2)”
- 只要是有括號的題目, 我們都會再遇到右括號(close parentheses)的時候, 需要先計算括號內的res_in_paren再把這個res_in_paren和左括號(open parentheses)左邊的res做合併.
- 這是經典的string parsing 算法題, 我們都是用stack來破題, 時間複雜度是O(n), 因為我們算法只需要掃過一遍字串,空間複雜度是O(n) 因為我們用了stack.
Related Problems in LC:
224. Basic Calculator
227. Basic Calculator II
772. Basic Calculator III
2021–2022刷題重點:
一道题多做
- 多总结
- 做related的题目
- 重复做了之前做过的题目
- 总结是王道
- 另外我没有遇到原题所以刷那么多题没有用
- 关键是做过了的就会
- 我都是一道题刷几遍最后我面之前
- 我只要做过的题目我能bugfree或者只有typo的写出来
- 為了增加coding 速度和實際面試一樣, 有個初步想法就可以開始尻code, 在做dry run 的動作.
重溫經典系列:
- 題號前400題
- 刷高頻提升會考的知識點的覆蓋率(廣度)
- 刷tag提升會考的知識點的熟練度(深度)
- 週末做contest or mock interview, 有計時, 增加臨場感, 且也可以查漏補缺知識點.
- 每兩週換一個topic
什麼是Feed Based Feed System?
經典的就是Tweeter’s Feed, Facebooks Timeline, IG’s story.
Problem Statement
和一般的推薦系統相比, 除了given user的資訊, 我們多了user的social graph(一種relationship between others)! Followers and Following!
Model
Rule-Based:把given user的所有follower的tweet根據時間反向排序(reverse chronological order)
轉成Ranking 問題
Why do you need to be familiar with evaluation metric?
Some pattern about continuous subarray related problem. Usually, naive solution is generate all possible subarray, which takes O(n²) times at least. And optimal solution is the one with special data structure such as prefix sum, monotone stack, in most of cases. And, this is tricky. So, I try to summarize what I learned in this post.
Note
1.包含當前element cur, 有多少個subarray的公式?
2.做subarray要注意的edge case:
