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)
Given 一個string expression, 我們要去計算result of expression.
1.是string裡面只有+-(), 沒有乘除. (See LC 224)
2.再來是有+-*/但沒有() (See LC 227)
3.最難版本是+-*/和()都有(See LC 772)
Related Problems in LC:
224. Basic Calculator
227. Basic Calculator II
772. Basic Calculator III
什麼是Feed Based Feed System?
經典的就是Tweeter’s Feed, Facebooks Timeline, IG’s story.
和一般的推薦系統相比, 除了given user的資訊, 我們多了user的social graph(一種relationship between others)! Followers and Following!
Rule-Based:把given user的所有follower的tweet根據時間反向排序(reverse chronological order)
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.
1.包含當前element cur, 有多少個subarray的公式?
Q1:What’s the total number of subscribers on the platform?
Q2:How many daily active users?
Hence, you have to build a system for a large number of users who require good recommendations on a daily basis.
“Given a user and context (time, location, and season), predict the…
This posts focus on those ML fundamentals.
There’re two steps to prepare for ML interview.
Step1: Understanding those fundamentals and theories to ensure we can answer those questions very well in the interview
Step2: To implement those code to ensure we can explain in detailed way!
Q1: Could you explain…
What is data stream?
It’s constant stream of data. For example, twitter messages and online news article.
Usually, for data stream related problem, there’s add function which will keep adding data from data stream into data structure you choose once it’s called. …
Some pattern about split string/array related problem. Usually, naive solution is generate all possible split, which takes exponential running time. And optimal solution is greedily split in most of cases. And, this is tricky. So, I try to summarize what I learned in this post.