2021刷题打卡

2021/07/28

FB - Dynamic Programming

140. Word Break II

• Backtracking + recursion (dfs)
  

2021/07/28 - 2021/07/29

DDIA: 3 Chapters

6. Partitioning

• Partitioning and Replication
• Partitioning of Key-Value Data
• Partitioning by Key Range
• Partitioning by Hash of Key
• Skewed Workloads and Relieving Hot Spots
• Partitioning and Secondary Indexes
• Partitioning Secondary Indexes by Document
• Partitioning Secondary Indexes by Term
• Rebalancing Partitions
• Strategies for Rebalancing
• Operations: Automatic or Manual Rebalancing
• Request Routing
• Parallel Query Execution
• Summary
  

7. Transactions

• The Slippery Concept of a Transaction
• The Meaning of ACID
• Single-Object and Multi-Object Operations
• Weak Isolation Levels
• Read Committed
• Snapshot Isolation and Repeatable Read
• Preventing Lost Updates
• Write Skew and Phantoms
• Serializability
• Actual Serial Execution
• Two-Phase Locking (2PL)
• Serializable Snapshot Isolation (SSI)
• Summary
  

8. The Trouble with Distributed Systems

• Faults and Partial Failures
• Cloud Computing and Supercomputing
• Unreliable Networks
• Network Faults in Practice
• Detecting Faults
• Timeouts and Unbounded Delays
• Synchronous Versus Asynchronous Networks
• Unreliable Clocks
• Monotonic Versus Time-of-Day Clocks
• Clock Synchronization and Accuracy
• Relying on Synchronized Clocks
• Process Pauses
• Knowledge, Truth, and Lies
• The Truth Is Defined by the Majority
• Byzantine Faults
• System Model and Reality
• Summary
  

2021/07/30

FB - Monotonic Stack

42. Trapping Rain Water

• DP: forward and backward to calculate leftMax and rightMax
• Monotonic stack: keep a decreasing monotonic stack to find the tapping water area
• The key is to draw the diagram.
  

239. Sliding Window Maximum

• Using a two way linked list, and the key is to keey the linked list monotinic decreasing, so the first element is always the largest one.739. Daily Temperatures
  

739. Daily Temperatures

• Encounters the first non-monotonic number, then we will start poping out
• The other key is to store index instead of the value in the deque/stack
  

503. Next Greater Element II

• After exercise on the other 3 similar problems, I am able to solve this. However, missed one use case for a list of  decreasing numbers [5, 4, 3, 2, 1]. Able to solve this use case by myself as well.
  

FB - Dynamic Programming

983. Minimum Cost For Tickets

• Count on 365 days / count on travel days.
  

2021/07/31

带娃的一天

2021/08/01
        
1216. Valid Palindrome III

• top-down dp with memorization
  

935. Knight Dialer

• graph traversal
  

1027. Longest Arithmetic Subsequence

• O(N^2) solution that is a little difficult to envision the solution.
  

复习
827. Making A Large Island

• 基本上可以做到bug free.
  

✅ HashTable
✅ Depth-First Search
✅ Dynamic Programming
⭕ Union Find
⭕ Backtracking
⭕ Divide and Conquer
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Heap (Priority Queue)
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum


2021/08/02
FB - Dynamic Programming
329. Longest Increasing Path in a Matrix

• DFS + memo: identify the base case: if the counter reaches current node, we should add 1 to the total length, and if it's out of range for neighbors, or does not meet the criteria, we won't pass the counter in to the neigbor cell.
• Topological sort: construct outdegree, BFS
  

691. Stickers to Spell Word

• The changed state is the new string. For each action, we are going to apply each sticker, and evaluate the shortest path.
  

10. Regular Expression Matching

• top-down + memo: using memo[j] to track if s.substring(i) isMatch p.substring(j);
  
  

Graph

1168. Optimize Water Distribution in a Village

• minimum spanning tree (prim's algorithm)
  

✅ HashTable
✅ Depth-First Search
✅ Dynamic Programming
⏹ Union Find
⭕ Backtracking
⭕ Divide and Conquer
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Heap (Priority Queue)
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum

2021/08/03
Union Find

1.     class UnionFind {
   
2.         int[] parent;
   
3.         
   
4.         public UnionFind(int n) {
   
5.             parent = new int[n];
   
6.             for(int i = 0; i< n; i++) {
   
7.                 parent[i] = i;
   
8.             }
   
9.         }
   
10.         
    
11.         public int find(int x) {
    
12.             if(parent[x] != x) parent[x] = find(parent[x]); // path compression
    
13.             return parent[x];
    
14.         }
    
15.         
    
16.         public void union(int x, int y) {
    
17.             int rootX = find(x);
    
18.             int rootY = find(y);
    
19.             parent[rootX] = rootY;
    
20.         }
    
21.     }

复制代码

721. Accounts Merge

• merge the emails as unique set, step 1: union, step 2: find the root and add to list
  

1361. Validate Binary Tree Nodes

• Perfect example to exercise the union-find algorithm
  

Graph
200. Number of Islands

• DFS
  

778. Swim in Rising Water

• translate to a problem to find a minimum weight path, and in this path find the maximum weight.
• Use a priorityQueue to store the node, sorted by weight. + BFS
  

1102. Path With Maximum Minimum Value

• Same question as #778
  

复习
90. Subsets II






[/i]

✅ HashTable
✅ Depth-First Search
✅ Dynamic Programming
✅ Union Find
⭕ Backtracking
⭕ Divide and Conquer
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Heap (Priority Queue)
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum

2021/08/04
Union Find
1361. Validate Binary Tree Nodes

• A nice question to exercise unionFind. Three criteria to ensure it'a a valid binary tree: 1) the child cannot belongs to multiple parents 2) there shouldn't be a cycle: if child's root equals to the new parent's root, it means there is another path to the same root so there is a cycle 3) there should be only one root
  

1559. Detect Cycles in 2D Grid

• Spent a whole afternoon trying to solve this probelm :(
• Union find is a nice solution O(logN) to do union-find: O(mn*logmn)
• For DFS, once we ensure we don't move backwards to the previous position, it would be obvious.
  

Pretty useful:::花花酱 Disjoint-set/Union-find Forest - 刷题找工作 SP1
737. Sentence Similarity II

• Transitive similarity, so we can build disjoint set by union find.
• There are still some pitfalls we want to avoid in this problem: what if the word shows up in the sentence not in the dictionary
  

547. Number of Provinces

• Good practice as well.
  

Graph
785. Is Graph Bipartite?

• Coloring the nodes layer by layer, BFS /DFS both works.
• One corner case is if the graph have multiple nodes, we need to iterate all the sub-graphs.
  

✅ HashTable
✅ Depth-First Search
✅ Dynamic Programming
✅ Union Find
⏹ Backtracking
⭕ Divide and Conquer
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Heap (Priority Queue)
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum

2021/08/05
Backtracking (DFS)

301. Remove Invalid Parentheses

• BFS: remove open/closed parenthesis layer by layer, if found the valid string, stop propagate to child layers.
• DFS: step 1. Find how many left parentheses and right parentheses needs to be removed; step 2. start removing parenthesis and do DFS. One trick here is we need to remove all the right parentheses first then remove the left parentheses.
  

282. Expression Add Operators

• https://www.youtube.com/watch?v=v05R1OIIg08
• Keep several state: prevExpression, prevNodeValue, prevGroupSum, position and the trick is for multiply operator, currGroupSum = prevGroupSum - prevNodeValue + prevNodeValue*currValue
  

78. Subsets
39. Combination Sum
113. Path Sum II
51. N-Queens

• 经典backtracking问题。卡在了怎么revert board。后来发现这种chess其实都没有必要存board，而只要存column和对角线就可以，这样revert/backtracking起来就很方便。另外，加result的时候肯定得res.add(newString(board)), res.add(board)的话board就会backtrack成空的list。
  

22. Generate Parentheses

• Parenthesis -> open, close, max...
  

2021/08/06 - 2021/08/07
带娃、DDIA

9. Consistency and Consensus

• Consistency Guarantees
• Linearizability
• What Makes a System Linearizable?
• Relying on Linearizability
• Implementing Linearizable Systems
• The Cost of Linearizability
• Ordering Guarantees
• Ordering and Causality
• Sequence Number Ordering
• Total Order Broadcast
• Distributed Transactions and Consensus
• Atomic Commit and Two-Phase Commit (2PC)
• Distributed Transactions in Practice
• Fault-Tolerant Consensus
• Membership and Coordination Services
• Summary