时隔两年，我又来刷题面狗家了

上周刚被狗家recruiter撩，约上了1/12的店面（之前ng时候走到过onsite，这次居然不能skip，好吧）


补充内容 (2022-01-01 05:20 +8:00):
买了利口premium，计划直接按照Google tag的频率开始刷，每天4题吧

补充内容 (2022-01-24 14:54 +8:00):
店面直接被鸽。。不过recruiter神奇说道直接帮我skip店面，约上了2月18的昂赛。。

楼主快别这里打卡了，万一面你的国人看到了，就不出你刷的题，可惜了。

别用英文吧。。

Monday 1/10

- Random Pick with Weight: construct prefix sum array, then randomly pick a number between (start, end), use binary search to find the interval

- Evaluate Reverse Polish Notation: stack

- Maximum Points You Can Obtain from Cards: construct prefix sum and suffix sum, then iterate through all combination from left k right 0 to left 0 right k, to find out which one has the highest number

- Number of Boomerangs: construct dist difference hashmap, store frequency, at the end, if frequency >= 2, the combination logic could be n!

- Decode String:
upon seeing a ']', pop stack until seeing a '[', then pop, then pop digit, read digit as binary, then push push str list reversely into stack again

- New 21 Game: probability game, observe that "n or few points" means p[n] + p[n-1] +...+p[1], construct a dp array, sum them up by 1/maxPts

- Split Array Into Consecutive Subsequences:  fundamentally, this problem is about making decision between for each point, whether insert into an existing tuples, or create a new one, and since the order has already been sorted, if you have to create a new one, and previous ones don't reach 3, that means false.

Monday 12/27

- Find Leaves of Binary Tree: the key is to leverage height() algorithm to find each leaf's height, store into pair, and then sort the pair to collection the answer.

- Guess the Word: each time call the guess API, return the answer, then compare all existing strs, remove all strings that is not x chars different than the current word.

- Shortest Path in a Grid with Obstacles Elimination: use BFS to guarantee finding the shortest path, use elimination of obstacles as much as you can, because if you make to the end it must be the shortest path.

- Maximum Number of Points with Cost: DP solution - 2D array with i represents the row, and j represents if I select point[i][j], what would be my maximum gain.

给小哥哥加油打气

rachaelsun 发表于 2021-12-28 00:13:38
给小哥哥加油打气

我家宝贝来看我啦，YAY

Tuesday 12/28

- Snapshot Array: use HashMap to store key: index, value: snap_id, upon searching, starting from the latest snap_id, backtrace until find a one with snap_id, return the value.

- Asteroid Collision: push positive val into stack, upon seeing negative, pop

- Find Original Array From Doubled Array: sort first, then use set to compare

- Logger Rate Limiter: ?? Too easy.. one time pass

是分天VO 的？赞楼主的分享

Wednesday 12/29

- FInd And Replace in String: construct a new obj Data, associate indices, sources and targets into the array, leverage the "startWith" method in String API

- Longest String Chain: DFS from the last word, keep deleting one char at a single time, use StringBuilder to perform deleteCharAt, use Set to avoid duplication, use Map to memoize (dynamic programming) to remember certain branches max outcome.

- Number of Matching Subsequences: two pointers

- Number of Islands:
1. recursively DFS O(m*n)
2. iteratively BFS, for each grid, construct a queue<Pair<Row, Col>>, *note: do the preprocess before
3. union find: construct two arrays, one for parent index, one for its corresponding rank, then iterate through all the grids, upon seeing "1", perform union from all the four dimensions, at the end, return getCount(), which is the number of disjoint sets.  O(m * n);

easyham 发表于 2021-12-31 12:08
Wednesday 12/29

- FInd And Replace in String: construct a new obj Data, associate indices, source ...

Follow up:
- Redundant Connection: very good practice for union find.

Friday 12/31
- Minimum Difference Between Largest and Smallest Value in Three Moves: fundamentally, it's a circular sliding window problem, for n moves, you have n possibilities, use mod to enumerate overflow indices. and Math.min to compare each scenarios