Han Zhu's Study Notes

Race Condition: Race condition occurs when the result of some computation depends on the exact timing of multiple threads of execution, i.e., the order in which the instructions are executed. Code that updates a variable can be broken into several assembly lines. Because the code is not atomic, if multiple threads are updating a variable at the same time, the result is undetermined. Consistency: Ideally, it shouldn't make a difference whether the requests are executed concurrently or not. We need a consistency model that specifies how the system should behave in the presence of consistency. The strictest model is sequential consistency, which states that the result of any execution is the same as if the operations of all the processors had been executed in a sequential order. Mutual Exclusion: Code has a critical section where accesses from other threads to the same shared resources will cause problems. To solve this problem, we need mutual exclusion. The idea ...

What is a Process? A process is a program in execution with its associated data and execution context. It's not the same as program or application, which may be running zero, one, or multiple times. Each instance of a running program is a separate process with its own address space and other context. When a program is compiled into an executable, the executable lives in secondary memory (hard disk). When the operating system runs the executable, it creates a process, which is essentially a data structure containing information about the program, in the main memory (RAM). A process has the following attributes: Process id. Program counter. Process state. Priority. General purpose registers. List of open files. List of open devices. Protection. All of these attributes are stored in a process control block (PCB). The PCBs of all processes are chained in a linked list. So by looking at this list, we can know the information of all executing processes. What i...

What is a back step? In definition, you do a back step when one of your hip is closer to the wall than the other, and both of your knees are pointing in the same direction, like this: In extreme cases, the knee in the back can be even lower than your feet, like this: That's why this technique is also called drop knee or Egyptian. Now you must be thinking, "whoa this looks quite comfortable. Why does anybody want to do this". In fact, back step is not as uncomfortable as it seems. It actually makes you feel more "comfortable" in the sense that you can climb more efficiently if you do it often. So how is back step useful? 1. Back step makes your center of gravity closer to the wall than regular positioning. In the above picture, the center of gravity of the climber is closer and closer to the wall from left to right. As we can see, when our body is facing the wall, our knees inevitably prevent us from pulling our core close to the wall. Using ...

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000. Example 1: Input: "bbbab" Output: 4 One possible longest palindromic subsequence is "bbbb". Example 2: Input: "cbbd" Output: 2 One possible longest palindromic subsequence is "bb". Thought process: Sub-problem: f( i, j ) = the LPS's length in the substring s( i, j ) Function:  If s[ i ] == s[ j ], f( i, j ) = f( i + 1, j - 1 ) + 2. Else, f( i, j ) = max( f( i + 1, j ), f( i, j - 1 ) ). Initialization: if i == j, the string has only one character. Its LPS's length is 1. Result: f( 0, length of s ). Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public class Solution { public int longestPalindromeSubseq ( String s ) { if ( s . length () == 0 ) { return 0 ; } int [][] ...

Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given  [10, 9, 2, 5, 3, 7, 101, 18] , The longest increasing subsequence is  [2, 3, 7, 101] , therefore the length is  4 . Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O( n 2 ) complexity. Follow up:  Could you improve it to O( n  log  n ) time complexity? Thought process: Dynamic programming: Sub-problem: f[ i ] = the longest increasing subsequence that ends at array[ i ]. Function: f[ i ] = max( f[ j ] ) + 1, where array[ j ] < array[ i ] Initialization: if the array has only one number, its LIS is 1. f[ 0 ] = 1. Result: the maximum element of f, because the LIS can end at any number. Solution 1 (DP): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public class Solution { ...

All climbing holds have directions. For the hold below, the arrow's direction is the most ideal hold position. We should always match our hold to the ideal loading direction, in order to climb efficiently. Holds can be categorized according to their directions. We have holds that point towards the body: And also the ones that point away from the body: A hold that points towards us is generally better than its counterpart which points away from us. To improve hold quality, it's always good to keep the body as close to the wall as possible. We talked about this in foot positioning . However, when it comes to foot holds, this rule doesn't always hold true. When the foot holds are big and clear cut, it's always ideal to keep the body close to the wall, in order to transfer more body weight to the feet. But when the foot holds are flat and slippery, or there are no foot holds at all, the quality of foot holds largely depends on friction. And there's a ...

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 6. Thought process: This problem is similar to 84. Largest Rectangle in Histogram . In that problem, I'm given an array of heights and asked to calculate the largest rectangle that can be formed by the heights. In this problem, I can keep an array of heights, which keeps track of the propagation of heights as I iterate through the matrix row by row. So the problem becomes calculating the largest rectangle in histogram for every row. Solution 1 (stack): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public class Solution { public int maximalRectangle ( char [][] matrix ) { int rowLength = matrix . length ; if ( rowLength == 0 ) { return 0 ; ...

A good gripping technique and understanding when to use what kind of grip can help a climber progress faster and prevent finger injury. What are the common gripping techniques? Three fingers open grip: Four fingers open grip: Half crimp: Full crimp: These grips are listed in the order from weaker to stronger, but also from less aggressive to more aggressive to your fingers. What are the common hold types? Sloper: Pocket: Edge: Pinch: Side pull: Undercling: Jug: The main takeaway today is that there is always the least aggressive way to take a hold, and the most aggressive way to take the same hold.  For example, this sloper can be taken more openly and less aggressively like this, or more aggressively in a crimpy way like this. Similarly, a pinch can be taken in a pinch (less aggressive), or in a full crimp (more aggressive), etc. To prevent finger injury, we need t...

You are given coins of different denominations and a total amount of money  amount . Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return  -1 . Example 1: coins =  [1, 2, 5] , amount =  11 return  3  (11 = 5 + 5 + 1) Example 2: coins =  [2] , amount =  3 return  -1 . Note : You may assume that you have an infinite number of each kind of coin. Though process: Suppose we have coins [c1, c2, c3, . . . , cn]. The sub-problem is to find the fewest number of coins to make [amount - c1, amount - c2, amount - c3, . . . , amount - cn]. And our dynamic programming function is: f[i] = min(f[i - coins[0]], f[i - coins[1]], f[i - coins[2]], . . . , f[i - coins[n]]) + 1 Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class Solution { public int coinChange ...

Good body positioning can make your climbing much more efficient. To learn body positioning, we first need to know where is our body's center of gravity. Our center of gravity lies behind our belly buttons. It's pretty much at the middle of our body. This implies that when we're climbing, we should always move our core as close to the wall as possible. In principle, this is the major foundation of a good climbing style.  Why? In footwork , I mentioned it is a good technique to use our legs and feet to share the weight of our body with the arms. Moving our core close to the wall is a great way to achieve this.  In this picture, you can see that by moving his core towards the wall, the climber can let go of his hands completely, thus significantly save the energy of his arms. This picture is only to demonstrate how efficient we can be using good body positioning. When climbing, resting is often done by transferring body weight to the lower body and letting go o...

The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently. HackerLand has   cities numbered from   to  . The cities are connected by   bidirectional roads. A citizen has access to a library if: Their city contains a library. They can travel by road from their city to a city containing a library. The following figure is a sample map of HackerLand where the dotted lines denote obstructed roads: The cost of repairing any road is   dollars, and the cost to build a library in any city is   dollars. You are given   queries, where each query consists of a map of HackerLand and value of   and  . For each query, fi...