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)

Note:

Related Problems in LC:

224. Basic Calculator

227. Basic Calculator II

772. Basic Calculator III


2021–2022刷題重點:

一道题多做

重溫經典系列:


什麼是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:


Problem scope:

Q1:What’s the total number of subscribers on the platform?

Q2:How many daily active users?

Problem Formulation

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.

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.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store