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

这位亲 今天的🐶不是两年前的🐶了，貌似很多lowball

Saturday 1/1

- Employee Importance: construct map<id, employee list> then dfs to calculate sum

- Count Square Submatrices with All Ones: very smart solution -> for each '1' seen, look for all left, up and left up dp values, dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));

- Single-Thread CPU: two PQs, one stores the order of tasks to be enqueued, one stores all tasks that have been enqueued and ready for processed.

- Trapping Rain Water: stack, for any height[i] > height[i+1], push to stack, upon seeing height[i] > height[i-1], pop the stack, find bounded height and distance to calculate storing amount.

Sunday 1/2

- Stock Price Fluctuation: there is a trap that different timestamp may have the same price, so use a treemap to sort price (for O(1) getMax and getMin), the value is the freq of certain price appears. Upon updating, put into another normal hashmap for get Current use, and update treemap to reflect the price.

- sentence screen fitting: two pointers..

- shuffle an array: make sure you copy the array by calling clone(), for shuffling algorithm, use pointers to in-place swap elements to achieve the best space complexity.

- array of doubled pairs: fundamentally it's pairing problem between arr[i] and 2 * arr[i], make sure sort by absolute value, and then iterating and deleting from map.

Monday 1/3

- Find Duplicate Subtrees: the key is to print out the post-order traversal for each node, if they're the same string, store into the map and count frequency.
- Detect Squares: store map<row, Map<col, frequency>> for existing points, upon seeing new points, check x-axis align points, to determine the length, and then use this to search both left side and right side points to count.

Tuesday 1/4

- Course Schedule: two ways to do it, one is DFS with set to deduplicate multiple visited nodes; the other way is using topological sort, by continuing removing nodes with no outgoing edges, lastly compare if the removed edges number is equal to prerequisite length.

- Remove Nth Last Element from a linkedList: one pass method is that we can have two pointers, one go Nth steps first, then together two pointers go step by step until reaching the end of the list, now the left side pointer should be pointing to the element that needs to be removed.

- Search in Rotated Sorted Array: find the rotate pivot first, then according to number value, split the array into two parts, just binary search in one part.

别用英文吧。。

Thursday 1/6

- Implement Trie: array of 26 size, construct a TrieNode class, contains put(), get(), setEnd(), isEnd(), containsKey() operation.

- Serialize and Deserialize Binary Tree: preorder DFS traversal. make sure you mark 'null' for the leaf nodes.

- Merge Two Sorted Linked: dummy node, nothing fancy.

- Merge K Sorted List:
1. Arrays.sort(), then create Node one by one. O(nlogn)
2. Insert into a priority queue, pop one by one O(nlogk)
3. k pointers O(nk)
4. divide and conquer, it's already been divided, just need to merge (call merge two sorted list to finish) O(nlogk)

Friday 1/7

- Longest Arithmetic Subsequence of Given Difference: 1D dp array, for each element, store from start point up until this point's maximum possible length, the trick here is don't need to iterate through the loop again, just finding the difference, have a hashmap to look up. that should reduce the time complexity to O(n)

- Minimum Maximum Pair Sum in Array: sorting.. and check the max one

- Swap Adjacent in LR String: the key here is to keep in mind for L, start must have it before end, and for R, start must have it after end.

- Time Based Key-Value Store: Map<String, Map<Integer, String>>.

- Longest Absolute File Path: first split up the \n, then for each element count how many tabs it has, compare to the existing tab, use stack as a data structure, to maintain the current list of elements, upon seeing a dot, build up the string and check if it's the global max.

Saturday 1/8

- Car Fleet: map position -> speed, sort position, starting from largest distance, check if one can catch one, use a pointer to traverse, check until finding a position that cannot catch up, end for this fleet, start another fleet from there.

- RLE Iterator: just simply use a counter to maintain the current counter index, or you can try to pre-process the array such that it was a normal array, and then just call next;

- Bulls and Cows: construct secret map, upon seeing a matching, if the index matches as well, it's a bull, and decrement cow, else it's a cow, and decrement the frequency map

- Valid Square: sort based on x-axis value first, then check if four lines are equal and also the diagonal lines are equal and not 0, only all conditions are met can prove this four points form a valid square.

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.