loudcoder.
← The notebookStudy notes

Algorithms &
data structures.

Yiping Deng·

Original study notes, preserved from the archive.

1 algorithms

1.1 graph algorithms

1.1.1 bredth first search

1.1.2 depth first search

1.1.3 minimal spanning tree

  1. Prim
  2. Kruskal

1.1.4 dijkstra

1.2 sorting

1.2.1 quick sort

leetcode 75

1.2.2 merge sort

1.2.3 heap sort

1.2.4 counting sort

leetcode 72 This is a effective sorting algorithms.

1.3 binary search

leetcode 33 leetcode 81 

int binary_search(vector<int>& nums){
  int lo = 0;
  int hi = nums.size() - 1;
  while(lo <= hi){
    int mid = lo + (hi - lo) / 2;
    if(nums[mid] == target)
      return target;
    else if(nums[mid] < target){
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
    return -1; //not found
  }
}

The code above is a while loop based binary search. The total running time is O(n log n).

For changed question like find in rotated sorted array, there are two approaches. First, we can directly find, break into cases where nums[mid] > nums[hi], nums[mid] = nums[hi], nums[mid] < nums[hi], and apply binary search accordingly. Second, we can also find the point of rotation and use the normal binary search with a bijective mapping.

1.4 divide & conquer

leetcode 84 Two typical example of divide and conquer algorithms:

  1. Maximum subarray

Maximum subarray problem is closely associated with our life. Imagine if you know the future stock market prices for a given period, and you want to maximize your profit.(Decide the optimum point to buy and sell). You are only allowed to do such operation once. The Stock price is given as a array with each entry representing the market price at that day. To tackle the problem, our first step is to precompute the difference between two days. A n element array will lead to a difference array of n - 1 items. Then we find a subarray that maximize the sum. Idea is, for any given point in the array, the maximum is either at the right side of the point, left side of the point or span across the point. Using this, we can build a recursion.

  1. Largest Rectangle in Histogram

This problem can be solved similarly to question 1, we expand greedily, divide across three cases.

1.5 backtracking

leetcode 39 leetcode 40 leetcode 46 general approach leetcode 51 leetcode 52 leetcode 78 Backtracking is just a DFS. Upon failure, we go back and find other possiblities. One easy to explain example is Sodoku solver, we eagerly find all the possible solutions and quit. This link gives a summary of backtracking.

In C++, one trick to obtimize the solution is to pass the aggregator as reference. It will yield much better result.(Just push the result in first, and pop it out later) Another way to obtimize is to use a loop to extend the selection process.(partially expand the recursion)

Queen Problem is also one of the backtracking problem. The general idea is the same, goin, if it doesn't work, recover.

1.6 two pointers

leetcode 76 leetcode 11 The problem with sum(twe sum, three sum, four sum.) All these can be solved using two pointers. First sort, and then find. Also, there are certain type of substring search problem that can also be solved using two pointers.(Leetcode 76)

Leetcode 11 is a typical example of two pointer problems. You are ask to maximize the water it can hold. Idea/Proof:

  1. The widest container (using first and last line) is a good candidate, because of its width. Its water level is the height of the smaller one of first and last line.
  2. All other containers are less wide and thus would need a higher water level in order to hold more water.
  3. The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further consideration.

1.7 dynamic programming

leetcode 31 leetcode 62 leetcode 63 leetcode 72 Just store it in a array so that we don't repeat computations.

Also, in some cases, buttom-up approach might lead to better run time(because we don't have a stack).

1.8 sweep line algorithm

1.9 greedy algorithm

leetcode 45 Greedy algorithms are a way to find global optimum. We greedily use local optimum to solve the global optimum. One typical example of such algorithms is the Jumping Game. Usually, can solve it using dynamic programming. However, such approach might lead to O(n2) algorithms. We can combine the idea of greedy algorithm and dynamic programming, forming a even faster solution.

1.10 string search

1.10.1 general approach to most substring problem

leetcode 76

Solution is straight forward, idea is matching from the right, and then shrink if possible, if not, continue moving the right. 

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> map(128, 0); // a hashmap

        for(char c:t) map[c]++; // count the number

        int left = 0, right = 0, counter = t.size(), min = 0x7fffffff, head = 0;

        while(right < s.size()){
            if(map[s[right++]]-- > 0) counter--; // reduce both the counter and the map

            // possible solution, try to shrink the answer
            while(counter == 0){
                // repeat if valid
                if((right - left) < min){
                    min = right - (head = left);
                }

                if(map[s[left++]]++ == 0){
                        // if it is a character required by t, make it invalid
                        counter++;
                }
            }
        }
        return min == 0x7fffffff ? "" : s.substr(head, min);
    }
};

I will first give the solution then show you the magic template.

The code of solving this problem is below. It might be the shortest among all solutions provided in Discuss. 

string minWindow(string s, string t) {
        vector<int> map(128,0);
        for(auto c: t) map[c]++;
        int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
        while(end<s.size()){
            if(map[s[end++]]-->0) counter--; //in t
            while(counter==0){ //valid
                if(end-begin<d)  d=end-(head=begin);
                if(map[s[begin++]]++==0) counter++;  //make it invalid
            }  
        }
        return d==INT_MAX? "":s.substr(head, d);
    }

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below. 

int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){ 

                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again

                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }

The code of solving Longest Substring with At Most Two Distinct Characters is below: 

int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> map(128, 0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++==0) counter++;
            while(counter>2) if(map[s[begin++]]--==1) counter--;
            d=max(d, end-begin);
        }
        return d;
    }

The code of solving Longest Substring Without Repeating Characters is below: 

int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++>0) counter++; 
            while(counter>0) if(map[s[begin++]]-->1) counter--;
            d=max(d, end-begin); //while valid, update d
        }
        return d;
    }

1.10.2 aho corasick algorithm

1.10.3 kmp algorithm

leetcode 28

The whole algorithm will be break into two part:

Part 1: building the failure function(a.k.a array): The whole algorithm is based on a idea: given a array failure and two index of the array, called i and j, i < j. If pattern[i] == pattern[j], then failure[j] = failure[i]. (Note: if we fail at i + 1, we will go to failure[i]) If there are not the same, we fail back to failure[i] and try it again until we hit the top.

Part 2: we now have a failure function. we simply perform check repetively on pattern and text, if not match, we fail back, do it again until hit the beginning.

Another way of implementation: KMP can also be viewed as a deterministic finite automata. However, DFA will require more memory, but the resulting algorithm will be faster. 

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length() == 0)
            return 0;
        if(haystack.length() == 0)
            // should not be empty string
            return -1;

        /**
        * building phase
        **/
        int failure[needle.size()];
        fill(failure, failure + needle.size(), -1); //fill the failure node with 0
        // we set the initial value of failure[0] to be -1

        for(int r = 1, l = -1; r < needle.size(); r++){
            while( l != -1 && needle[l+1] != needle[r])
          l = failure[l]; 
            //repeatively fall back until we get -1, the initial value, which exists at failure[0]

            if( needle[l+1] == needle[r])
          failure[r] = ++l; //normally we will increase the value of l at every iteration
        }

        /**
        * matching phase
        **/

        int tail = -1;
      for(int i=0; i < haystack.length(); i++) {

        while( tail != -1 && haystack[i] != needle[tail+1])
          tail = failure[tail];

        if( haystack[i] == needle[tail+1])
          tail++;

        if( tail == needle.size() - 1)
          return i - tail;
      }

        return -1;
    }
};

1.10.4 boyer-moore

1.11 techniques

  1. window sliding technique

    geeksforgeeks leetcode 30

    We use this technique to obtimize the O(n * k) algorithms. Instead of having a double for loop, we maintain a moving window. To move the window, you need to remove the previous item and add the next item in. If such operation takes constant time(independent of k and l), this optimization technique will yield a better result.

1.12 math

1.12.1 permutation

leetcode 31 wiki: generation in lexicographic order wiki: lexicographical order leetcode 46 leetcode 47 leetcode 60 leetcode 77 One interesting fact about permutation is that we can build a total order out of every permutation. Also, some quick sort algorithms uses random permutation to guarantee the average time of the algorithms. For leetcode question 31(next permutation), the right way to solve this question is that first make observation of the next permutation, and deduct the right way.(Considering how many are reversely sorted, and swap)

For generating all the possible permutation, we need to utilize the DFS nature. We swap in order, and swap back to keep it simple.

For leetcode 47, the DFS need a little work(add a hash map to keep track of duplicates). However, we can use a different approach. There is another approach leetcode 47 in 20 line. This approach is not backtracking, since we do not go back. Instead, the idea is to keep the array partial sorted.(Even after the swapping!) This sounds very interesting. This idea is very interesting. The for loop in recursion function keeps a loop invariant: all the element after index k remains sorted! Actually, the loop will explore all the possible way of keep element after k sorted. As the recursion dive deep, we will explore all the possibility, and, of course, when we reach the end, the loop invariant told us that we will be able to explore all the possible solution space. (Since there is no element after the last index). Such a elegant solution. As those people mentioned before, we don't need to make a copy every time. We can recover the state, so we can still improve this solution!

1.12.2 pigeonhole principle

leetcode 41 Pigeonhole principle is widely used in set theory. In Computer Science, we usually use it to solve questions that are associate with array. A common approach is to consider each slot of array as a pigeonhole.

In leetcode 41, according to pigeonhole principle, given k positive items in a array, the first missing positive must be between 1 and k + 1.(Consider the extreme case that it contains every elements from 1 to k.) Thus, we can use this approach to mark every "pigeonhole" and find the first unmarked slots. It will be the answer. Marking can be done if we flip a positive number to negative.

1.12.3 add minus mulitiplication divide pow

leetcode 43 This are normal functions implemented from scratch.

1.12.4 matrix operation

leetcode 48

1.12.5 edit distance

leetcode 72 This is a classic DP problem. First consider the edge cases: if one of the string is empty, the number of operation will be purely the number of charactor of other words.

Now, we first solve the subproblem. Having two words with length m and n, the number of changes required is simply the min(change with m - 1, n - 1 + 1(replace), change with m - 1, n + 1(delete), change with m, n -1 + 1(insert) ) Using such a operation, we can build this table from buttom up. 

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int i = 0; i <= n; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(word1[i - 1] == word2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1] + 1, min( dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }

        return dp[m][n];
    }
};

Notice that we actually don't need the entire dp, instead, we only need dp[i - 1][j - 1], dp[i - 1][j] and dp[i][j - 1]. If we create a dp with length m + 1, store dp[_][j - 1]'s value, use one variable to store dp[i - 1][j].

In practice, dp[i - 1][j] will be overwritten, we actually need a variable to store dp[i - 1][j - 1]. We call it previous. it will be sufficient. 

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        int dp[m + 1];
        for(int i = 0; i <= m; i++){
            dp[i] = i;
        }
        int previous;
        int tmp;
        for(int j = 1; j <= n; j++){
            previous = dp[0];
            dp[0] = j;
            for(int i = 1; i <= m; i++){
                tmp = dp[i];
                if(word1[i - 1] == word2[j - 1]){
                    dp[i] = previous;
                } else {
                    dp[i] = min(dp[i - 1] + 1, min(previous + 1, dp[i] + 1)); // dp[i] store the value in the previous row
                    //dp[i - 1] has been updated in the previous inner loop iteration.
                }
                previous = tmp; // recover the value dp[i - 1][j - 1]
            }
        }

        return dp[m];
    }
};

2 data strcture

2.1 stack

leetcode 31 leetcode 84 leetcode 85 There are many use cases for stack. The common use of stack is to store local variable in a programming language.

In C / C++, local variable are stored on stack. When a function is called, all its argument will be pushed into stack in a reversed order. Later, when we execute the called function, the local variable can be access just like the sequence of calling.(because we reversed it.)

Also, it is the stack that enables us to do a DFS search, while a queue empowers us with BFS.

Stack can be used to solve problems like matching parathesis. For example, leetcode 32. In leetcode 32, we push every '(' index onto the stack, if enconter ')', check if the stack top points to '('. If so, pop. If not, push the current index. The longest solution is between the index on the remaining stack after the main loop.

This is particularly useful in program parsing.

Leetcode 84 is another typical question that can be solved using stack. Idea:

  1. We can calculate the Largest Rectangle if the array is sorted(non-decreasing)
  2. We use a stack to maintain such a array and calculate the result on the fly
  3. Iterate over all numbers in sequence, if the current number is smaller than the stack top, we consider the two cases.

Case 1: we do not include the current, the max will be among those on the stack which are greater than current. We calculate accordingly Case 2: we include current, then just replace all the number that is greater then current with the current value, again push the current to the stack

  1. if the current number is greater or equal to the stack top, we can always include this number to make a even better result.

Code here: 

static const auto speedup = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:

    int largestRectangleArea(vector<int>& heights) {
        // idea: build a array that is always increasing.
        // such array is just a stack
        stack<int> stck;
        int area = 0;
        int count;
        for(int i = 0; i < heights.size(); i++){
            if(stck.empty() || stck.top() <= heights[i]){
                stck.push(heights[i]); // push back
            } else {
                count = 0;
                while(!stck.empty() && stck.top() > heights[i]){
                    count++;
                    area = max(area, stck.top() * count);
                    stck.pop();
                }
                while(count--){
                    stck.push(heights[i]); // push back the result
                }
                stck.push(heights[i]); // push the current in
            }
        } // end of loop, calculate the longest

        count = 0;
        while(!stck.empty()){
            count++;
            area = max(area, stck.top() * count);
            stck.pop();
        }
        return area;
    }
};

Leetcode 85 is a extension of leetcode 84. If we consider each row, and count the number of 1s on top of that row for each column, we can call it building. We basically are back to leetcode 84. Solution here: 

class Solution {
public:
    inline int largestRectangleArea(vector<int>& heights) {
        // idea: build a array that is always increasing.
        // such array is just a stack
        stack<int> stck;
        int area = 0;
        int count;
        for(int i = 0; i < heights.size(); i++){
            if(stck.empty() || stck.top() <= heights[i]){
                stck.push(heights[i]); // push back
            } else {
                count = 0;
                while(!stck.empty() && stck.top() > heights[i]){
                    count++;
                    area = max(area, stck.top() * count);
                    stck.pop();
                }
                while(count--){
                    stck.push(heights[i]); // push back the result
                }
                stck.push(heights[i]); // push the current in
            }
        } // end of loop, calculate the longest

        count = 0;
        while(!stck.empty()){
            count++;
            area = max(area, stck.top() * count);
            stck.pop();
        }
        return area;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0)
            return 0;
        if(matrix[0].size() == 0)
            return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int area = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = 1;
                    if(i > 0){
                        dp[i][j] += dp[i - 1][j]; // build the dp
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
            // after building each row, calculate the result
            area = max(area, largestRectangleArea(dp[i]));
        }
        return area;
    }
};

2.2 queue

2.3 linked list

leetcode 61 leetcode 86 Linked list are commonly use if you want quick head access, quick append, quick popback operation. There are also two variant of linked list: ring buffer and doubly linked list.

2.4 array

2.5 hash table

2.6 binary tree

2.6.1 binary search tree

  1. tranversal of the tree

leetcode 99 Different ways of tranverse the tree produces different results.

  1. In-order tranversal is the most important one. If you print

the value, it will produces a sorted array. Leetcode 99 uses this idea. We consider the binary search tree as a sorted array, then it becomes the problem to detect a swap of two elements in a sorted array. 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* fst;
    TreeNode* snd;
    TreeNode* prev;
    void find(TreeNode* root){
        // find the error
        if(root == NULL){
            return;
        }

        find(root->left);

        // in-order tranversal
        if(fst == NULL && prev->val >= root->val){
            // first disorder
            fst = prev;
        } 
        if(fst != NULL && prev->val >= root->val){
            snd = root;
        }

        prev = root;
        // end of in-order tranvsersal

        find(root->right);
    }
    void recoverTree(TreeNode* root) {
        fst = NULL;
        snd  = NULL;
        prev = new TreeNode(INT_MIN);
        find(root);
        swap(fst->val, snd->val);
    }
};
  1. recovery of binary trees

Given a preorder tranversal and inorder tranversal, recover the binary tree leetcode 105

Idea: we do it recursively. Where we use the inorder tranversal to find the size of left child tree and right child tree, and using such information to divide the preorder printing array. 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* solve(vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie){
        if(ps > pe || is > ie){
            return NULL;
        }
        TreeNode* rst = new TreeNode(preorder[ps]);

        int pos;
        for(int i = is; i <= ie; i++){
            if(inorder[i] == rst->val){
                pos = i;
                break;
            }
        }

        int l_size = pos - is;
        int r_size = ie - pos;

        rst->left = solve(preorder, inorder, ps + 1, ps + l_size, is, pos - 1);
        rst->right = solve(preorder, inorder, ps + l_size + 1, pe, pos + 1, ie);
        return rst;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return solve(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size());
    }
};

2.7 heap

2.8 union find

2.9 trie

2.10 segment tree

In the real world application, we aften faces situation which we want to do queries on a inteval. To support such operation, segment tree is introduced, and it has the following property:

  1. segment tree is a highly balenced binary tree
  2. every note of a segment tree represents a inteval, the father node's inteval represent the sum of two

chid nodes. Brother nodes' intevals never collapse.

  1. most operation is O(n log n).

The data has to satisfy the property of monad to use this operation. Example code of point update + inteval query(sum as the binary operator) 

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define UP(i,a,b) for(int i=a;i<=b;i++)
#define DN(i,a,b) for(int i=a;i>=b;i--)

struct node
{
  int l, m, r, sum;
} nd[4 * 50005];

void build(int i, int l, int r)
{
  nd[i].l = l;
  nd[i].r = r;
  nd[i].m = (l + r) / 2;

  if(l == r)
  {
    scanf("%d", &nd[i].sum);
    return;
  }

  build(i * 2, l, nd[i].m);
  build(i * 2 + 1, nd[i].m + 1, r);

  nd[i].sum = nd[i * 2].sum + nd[i * 2 + 1].sum;//At this point, two child trees have already been built up whose top nodes already have sum value
}

void update(int i, int n, int x)
{
  nd[i].sum += x;

  if(nd[i].l == nd[i].r) return;

  if(n <= nd[i].m)
    update(i * 2, n, x);
  else
    update(i * 2 + 1, n, x);
}

int query(int i, int a, int b)
{
  if(nd[i].l == a && nd[i].r == b)
    return nd[i].sum;

  if(b <= nd[i].m)
    return query(i * 2, a, b);

  if(nd[i].m < a)
    return query(i * 2 + 1, a, b);

  return query(i * 2, a, nd[i].m) + query(i * 2 + 1, nd[i].m + 1, b);

}

int main()
{
  char s[20];
  int t, n, x, a, b;

  scanf("%d", &t);

  UP(i, 1, t)
  {
    printf("Case %d:\n", i);
    scanf("%d", &n);

    build(1, 1, n);

    while(1)
    {
      scanf("%s", s);

      if(s[0] == 'A')
      {
        scanf("%d%d", &n, &x);
        update(1, n, x);
      }
      else if(s[0] == 'S')
      {
        scanf("%d%d", &n, &x);
        update(1, n, -x);
      }
      else if(s[0] == 'Q')
      {
        scanf("%d%d", &a, &b);
        printf("%d\n", query(1, a, b));
      }
      else break;
    }
  }
}

3 design pattern

4 system design

5 operating system

6 programming language

6.1 C++

6.1.1 speedup code

static const auto speedup = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

class VectorTools{
public:
    void sorted(vector<int>::iterator first, vector<int>::iterator last) {
        if (first == last || first + 1 == last) return;
        vector<int>::iterator pivot = first;
        int temp;
        for (vector<int>::iterator it = first+1; it != last; it ++) {
            if (*it<*pivot) {
                temp = *it;
                *it = *(pivot+1);
                *(pivot+1) = *pivot;
                *pivot = temp;
                pivot ++;
            }
        }
        sorted(first, pivot);
        sorted(pivot+1, last);
    }

    int binary_search(vector<int>::iterator first, int size, bool have_sorted, int tar) {
        int l = 0;
        int r = size - 1;
        int mid = (l+r)/2;
        if (size==0) return -1;
        else if (size==1) return 0;
        if (!have_sorted) sorted(first, first+size);
        if (*(first+l)>=tar) return l;
        if (*(first+r)<=tar) return r;
        while (l < r - 1) {
            mid = (l+r)/2;
            if (*(first+mid) < tar) l = mid;
            else if (*(first+mid) == tar) {
                int i = 0;
                while((mid - i)>=0 && *(first+mid-i) ==  tar) i ++;
                return *(first+mid-i)==tar?(mid-i):(mid-i+1);
            }
            else r = mid; 
        }
        return (tar-*(first+l) >= *(first+r) - tar)?r:l;
    }

    void vector_display(vector<int>& v) {
        for (vector<int>:: iterator it = v.begin(); it != v.end(); it ++) {
            printf("%d ",*it);
        }printf("\n");
    }
};

7 database