Yunrui Li

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:

  1. 上面這些題型都可以假設沒有leading negative integers. For example, “-3+2” or “(-3+2)”
  2. 只要是有括號的題目, 我們都會再遇到右括號(close parentheses)的時候, 需要先計算括號內的res_in_paren再把這個res_in_paren和左括號(open parentheses)左邊的res做合併.
  3. 這是經典的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 問題

--

--

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:

--

--

Yunrui Li

Yunrui Li

I’m Taiwanese expat. I’v worked in Singapore as data scientist after graduation from Taiwan and currently I work in Amsterdam as machine learning engineer.