Cache的三种pattern:write-through, write-around, write-back

Write-through: data is written simultaneously to the cache and disk storage. But the ack of the write is not sent to the application until the database write successfully completes the write.

Write-around: data is written to the database first, then a copy of that data promoted up to the cache.

Write-back: only update the cache and later the cache will update the database
asynchronously. However, the ack to the applications comes after the data is written to the cache, not to the database, which means ack occurs at the flash speed. But it may suffer data loss when cache fails before data has been flushed to the disk.

Comparing write-through, write-back and write-around caching

Advertisements

Matrix 跟Sequence的DP总结

Matrix的DP,二维数组

64 Minimum Path Sum: 对于每个点,只能往下走或者往右边走,所以每个点path sum的值来源于上面点或者左边点。
State: f[x][y]从起点走到x,y的最短路径
Function: f[x][y] = min(f[x-1][y], f[x][y-1]) + matrix[x][y]
initialize: f[0][0] = matrix[0][0], 对于二维数组要想f[i][0]跟f[0][i]如何初始化:
//f[i][0] = sum(0, 0 -> i, 0) 初始化最左边
//f[0][i] = sum(0, 0-> 0, i) 初始化最上边
Answer: f[n-1][m-1]

63 Unique Paths II,某些点不能走(obstacle),
不能走的点之间算为0就可以,用个if语句去check.

Sequence的DP,一维数组

State: f[i]表示”前i”个位置/数字/字母,
function: f[i]= f[j]….j是i之前的一个位置
initialize: f[0]..
answer: f[n-1]..

70 Climbing Stairs(爬楼梯)
state: f[i]表示前i个位置, 调到第i个位置的方案总数
function: f[i]=f[i-1]+f[i-2]
initialize:f[0]=1
answer: f[n]

  1. Jump Game
    state: f[i]表示能否从起点调到第i个位置
    function: f[i] = OR(f[j], j A[j] + j >= i && f[j]=true
    initialize: f[0]=true
    answer:f[n-1]

  2. Palindrome Partitioning II
    求最少的分割次数,
    state: f[i]为”前”i个字符组成的子字符串需要最少几次cut()
    function: f[i] = Min{f[j] + 1, j<i && j+1 ~ i 这段是一个palindrome}
    initialize: f[i]=i – 1(f[0]=0)
    answer:f[s.length()]

  3. Word Break
    state: f[i]为"前i"个字符能否被完美切分
    function: f[i]=OR{f[j], j<i, j+1 ~ i是一个词典中的单词}
    initialize: f[0]=true
    answer: f[s.length()]
    O(NL), N:字符串长度. L:最长单词的长度

120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

思路: DP的经典题目,用Divide&Conquer的思路来实现,每走一步都有两个选择: 往下走跟往右走. 总体来说走下来时间复杂度有点高为O(2^n). 简单写一下用DFS实现分治的解法

public int miniPath(int[][] triangle) {
    return dfs(triangle, 0, 0);
}

public int dfs(int[][], triangle, int x, int y) {
    if (x == triangle.length - 1) {
        return 0;
    }
    int left = dfs(triangle, x + 1, y);
    int right = dfs(triangle, x + 1, y + 1);
    return Math.min(left, right) + triangle[x][y];
}

同时给下traverse的思路:

//traverse
public void dfs(int[][] triangle, int x, int y, int sum) {
    if (x == triangle.length) {
        if (sum <  miniSum) {
            miniSum = sum;
        }
        return;
    }
    dfs(triangle, x + 1, y, sum + triangle[x][y]);
    dfs(triangle, x + 1, y + 1, sum + triangle[x][y]);
}

DFS过程中, 很多点被重复计算,导致时间复杂度特别高,我们可以加cache来降低时间复杂度.
把时间复杂度降到O(n^2).

class Point {
   int x;
   int y; 
   public Point(int x, int y) {
       this.x = x;
       this.y = y;
   }
}
public int dfs(int[][], triangle, Point point, HashMap<Point, Integer> map) {
    if (point.x == triangle.length - 1) {
        return 0;
    }
    if (map.containsKey(point)) {
        return map.get(point);
    }
    int left = dfs(triangle, point.x + 1, point.y);
    int right = dfs(triangle, point.x + 1, point.y + 1);
    Point newValue =  Math.min(left, right) + triangle[point.x][point.y];
    map.put(point, newValue);
    return map.get(point);
}

我们还可以用循环DP的方式来解决这个问题:
1. Down -> Top approach
2. Top-> Down approach
对于这个题目,如果我们从底部往上开始走,每层取最小值,

1. Down -> Top approach

// 状态定义
f[i][j] 用来表示i,j出发走到最后一层的最小路径长度
n = triangle.length;
// 初始化数组
for (int i = 0; i < n; i++) {
    f[n-1][i] = triangle[n-1][i];
}
// 循环递归求解
for (int i = n - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        f[i][j] = Math.min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
    }
}
// 求结果: 起点
f[0][0]

2. Top-> Down approach

对于本题,自顶向下的方法略复杂些,主要是因为要check一些边界条件:

// 状态定义
f[i][j] 用来表示0,0出发,走到i,j的最小路径长度
n = triangle.length;
// 初始化
f[0][0] = triangle[0][0]

// 循环递归求解
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= i; j++) {
        f[i][j] = OO
        if(i - 1, j 存在) {
            f[i][j] = Math.min(f[i][j], f[i-1][j]) + triangle[i][j];
        }
        if(i - 1, j - 1存在) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i][j]) + triangle[i][j]
        }
    }
}

// 求结果:
Math.min(f[n-1][0],f[n-1][1],f[n-1][2]…..);

DP的总结:

什么时候用DP来解呢? 一般有以下几个情况可以考虑用DP来做:
1. 求minimum或者maximum的问题
2. 求Yes/No的问题
3. 求个数(Count)的问题
4. 当给的条件不能sort或者swap的时候,可以考虑用DP

DP的四个要素

  1. 状态 State
  2. 转换方程Function
  3. 初始化(起点)
  4. 终点(答案)

大概面试中常见的DP类型

  1. MatrixDP(10%), 二维数组
  2. Sequence(40%), 一维数组
  3. Two Sequences DP(40%)
  4. Backpack(10%)

二维矩阵中Connected Cell问题(DFS)

HackerRank上面对Matrix中Connected Cell的模板, Leetcode中此类问题有island的个数,面积,surrounded regions等

dfs

public class Solution {
    public int getBiggestRegion(int[][] matrix) {
        int maxRegion = 0;
        int row = matrix.length, col = matrix[0].length;
        //boolean[][] visited = new boolean[row][col]; 

        for(int i = 0; i &lt; row; i++) {
            for (int j = 0; j &lt; col; j++) {
                if (matrix[i][j] == 1) { // 找到'1'岛屿
                    int size = getRegionSize(matrix, i, j);
                    maxRegion = Math.max(size, maxRegion);
                }
            }
        }
        return maxRegion;
    }

    public int getRegionSize(int[][] matrix, int row, int col) {
        // 1. boundary checks
        if (row &lt; 0 || col &lt; 0 || row &gt;= matrix.length || col &gt;= matrix.length){
            return 0;
        }
        // 2. check if it is the region
        if (matrix[row][col] == 0) {
            return 0;
        }
        matrix[row][col] = 0; // visited check, 也可以用一个visited数组来实现
        int size = 1; // initialize size is 1
        // explore 4 directions: left, right, up, down
        public int[] rowDir = new int[]{-1, 0, 1, 0};
        public int[] colDir = new int[]{0, -1, 0, 1};
        for (int i = 0; i &lt; 4; i++) {
            int newRow = row + rowDir[i];
            int newCol = col + colDir[i];
            if (newRow == row || newCol == col) continue; // 避免搜索自己
            size += getRegionSize(matrix, newRow, newCol);
        }
        matrix[row][col] = 1; // 搜索完了, 赋原有值
        return size;
    }


}

DFS四个方向搜索的时候,另一种写法

for (int r = row - 1; r &lt;= row + 1; r++) {
    for (int c = col - 1: c &lt;= col + 1; c++) {

    }
}

图的最短路径问题(BFS)

HackerRank上面简单总结下Graph中用BFS解决最短路径问题, 做BFS的时候需要用一个queue来记录nextToVist的所有点。

public class Graph {
    private Node[] nodes;
    private static EDGE_DISTANCE = 6;

    public Graph(int size){}
    public class Node{}
    public Node getNode(int id){}
    public void addEdge(int first, int second){}
    public int[] shortestReach(int startId) {
        LinkedList&lt;Integer&gt; queue = new LinkedList&lt;Integer&gt;();
        queue.add(startId); // 加入起始点

        int[] distances = new int[nodes.length];
        Arrays.fill(distance, -1); //如果没找到,默认距离为-1
        distances[startId] = 0 // 初始距离,start=&gt; start自己的距离为0
        // BFS
        while(!queue.isEmpty()) {
            int nodeIndex = queue.poll();
            for (int neighbor: nodes[nodeIndex].neighbors) {
                if (distance[neighbor] == -1){ // 没有被visit
                    distances[neighbor] = distances[nodeIndex] + EDGE_DISTANCE;
                    queue.add(neighbor);
                } 

            }
        }
        return distances;
    }
}

Binary Search(二分搜索)总结

数值相关的二分

67.Sqrt(x): 1 -> x的区间来二分.start=1,end=x; 最后边界条件先检查startstart<=x, 然后看endend0 return pow(x,n) 否则return 1/pow(x,Math.abs(n)); pow实现思路就是二分,if(n==0) return1;if(n==1) return x; half = pow(x,n/2);return (n % 2 == 0) ? halfhalf :halfhalf*x,
34,Search for a Range(搜索范围)/搜索duplicates: 可以两次二分查找分别找到给定target的起始点跟终止点. 注意每次二分搜索后start跟end的边界条件检查

一维数组跟二维数组里的二分搜索

  1. Search Insert Position: 给定数组是有序的,
    target array[length – 1] return length;
    array[0]nums[mid+1]) => true, if(nums[mid] <nums[mid-1]) end = mid;说明mid左边是单调递减的,应该往左边找。否则往右边找.

74.Search a 2D Matrix I: 给定的matrix中,下一行的头元素总是大于上一行的尾元素,整个二维数组中的元素是单调递增,一如何定位某一点的坐标, start=0, end= row*col-1; 某一点的表示matrix[index/col]
240.Search a 2D Matrix II: 从左下角开始 matrix[row – 1][0],往右上角搜索,如果当前点大于target就往上走,小于target就往右走

Rotated Sorted Array

153.Find Minimum in Rotated Sorted Array I: 153中不包括duplicate. 直接二分,target选最右边元素。 每次mid跟target进行比较,如果大于target,说明mid在左边逆序,最小值在右边,start=mid; 如果小于target,说明mid在右边,往左边找,end = mid; 最后再返回start跟end中较小的元素
154.Find Minimum in Rotated Sorted Array II: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;
33. Search in Rotated Sorted ArrayI:
因为rotate的缘故,当我们切取一半的时候可能会出现mid在左半边区间,或者右半边区间的情况,所以我们要做进一步的判断。假设数组是A,起始start,终止end,还有中间位置是mid。在每次迭代中,分三种情况:
A[mid] = target 找到target
A[mid] > A[start] 说明mid在左半边区间(4 5 6 7)有序的, 那么就要判断target是否在start与mid之间, 如果在的话则把m设为end边界, 否则的话target就在另外的一半, 把mid设为start边界
如果A[mid] < A[start], 说明mid在右半边区间(0 1 2 ), 那么就判断target是不是在mid到end之间.如果target在的话把mid设为start, 否则把mid设为end
最后再判断A[start],A[end]与target的关系
81. Search in Rotated Sorted ArrayII: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;

Graph, BFS, DFS的总结

HackerRank中对Graph的BFS跟DFS讲的不错,再次做个简短总结.
如下图所示
DFS: Go Deep. recursive的过程,需要flag,用来避免陷入infinite loop.
BFS: Go BOARD. iterative的过程, 需要用queue,来记录nextToVisit的点.
bfs-dfs
代码部分:

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * Created by dylan on 10/29/16.
 * Reference: https://www.youtube.com/watch?v=zaBhtODEL0w
 */
public class Graph {
    private HashMap&lt;Integer, Node&gt; nodeLookup = new HashMap&lt;Integer, Node&gt;();


    public Node getNode(int id) {
        if (!nodeLookup.containsKey(id)) return null;
        return nodeLookup.get(id);
    }

    private void addEdge(int source, int destination) {

    }

    public boolean hasPathDFS(int source, int destination) {
        Node s = getNode(source);
        Node d = getNode(destination);
        HashSet&lt;Integer&gt; visited = new HashSet&lt;Integer&gt;();
        return hasPathDFS(s, d, visited);
    }

    private boolean hasPathDFS(Node source, Node destination, HashSet visited) {
        if (visited.contains(source.id)) return false;
        visited.add(source.id);
        if (source == destination) {
            return true;
        }

        for (Node child: source.adjacent) {
            if (hasPathDFS(child, destination, visited)){
                return true;
            }
        }
        return false;
    }

    public boolean hashPathBFS(int source, int destination) {
        return hasPathBFS(this.getNode(source), this.getNode(destination));
    }

    private boolean hasPathBFS(Node source, Node destination) {
        LinkedList&lt;Node&gt; nextToVisit = new LinkedList&lt;Node&gt;();
        HashSet&lt;Integer&gt; visited = new HashSet&lt;Integer&gt;();
        nextToVisit.add(source);
        while(!nextToVisit.isEmpty()) {
            Node node = nextToVisit.remove();
            if (node == destination) {
                return true;
            }

            if (visited.contains(node.id)) {
                continue;
            }
            visited.add(node.id);

            for (Node child: node.adjacent) {
                nextToVisit.add(child);
            }
        }
        return false;

    }


    public static class Node {
        private int id;
        LinkedList&lt;Node&gt; adjacent = new LinkedList&lt;Node&gt;();
        private Node(int id) {
            this.id = id;
        }
    }

}