Saturday, July 16, 2016

LeetCode 375 - Guess Number Higher or Lower II


http://bookshadow.com/weblog/2016/07/16/leetcode-guess-number-higher-or-lower-ii/
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Hint:
  1. The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the first scenario.
  2. Take a small example (n = 3). What do you end up paying in the worst case?
  3. Check out this article if you're still stuck.
  4. The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
  5. As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?

题目大意:

我们玩猜数字游戏。游戏如下:
我从1到n中选择一个数字。你需要猜我选的是哪个数字。
每一次你猜错,我都会告诉你数字是高了还是低了。
然而,当你选择某个数字x并且猜错,你需要支付$x。当你猜到我选的数字时胜出。
测试用例如题目描述。
给定n ≥ 1,计算你需要多少钱才可以确保赢得游戏。
提示:
  1. 游戏的最佳策略是最小化你面临的最大可能损失。另一种策略是最小化期望损失。在这里,我们关注第一种策略。
  2. 以一个小的输入为例(n = 3)。最坏情况下你会支付多少金额?
  3. 如果还是一筹莫展,可以参考这篇文章
  4. 单纯的minimax递归实现即使对于很小的n都是非常耗时的。你必须使用动态规划。
  5. 作为思考题,你怎样修改代码来实现最小化的期望损失,而不是最小化的最坏损失?
 374 Guess Number Higher or Lower 中,我们采用二分法来进行查找,但这题并不是用二分法。
这题要求我们在猜测数字y未知的情况下(1~n任意一个数),要我们在最坏情况下我们支付最少的钱。也就是说要考虑所有y的情况。
我们假定选择了一个错误的数x,(1<=x<=n && x!=y )那么就知道接下来应该从[1,x-1 ] 或者[x+1,n]中进行查找。 假如我们已经解决了[1,x-1] 和 [x+1,n]计算问题,我们将其表示为solve(L,x-1) 和solve(x+1,n),那么我们应该选择max(solve(L,x-1),solve(x+1,n)) 这样就是求最坏情况下的损失。总的损失就是 f(x) = x + max(solve(L,x-1),solve(x+1,n))
那么将x从1~n进行遍历,取使得 f(x) 达到最小,来确定最坏情况下最小的损失,也就是我们初始应该选择哪个数。
上面的说法其实是一个自顶向下的过程(Top-down),可以用递归来解决。很容易得到如下的代码(这里用了记忆化搜索)

动态规划(Dynamic Programming)
参考:https://discuss.leetcode.com/topic/51356/two-python-solutions
状态转移方程:
dp[i][j] = min(k + max(dp[i][k - 1], dp[k + 1][j]))
其中dp[i][j]表示猜出范围[i, j]的数字需要花费的最少金额。
def getMoneyAmount(self, n): """ :type n: int :rtype: int """ dp = [[0] * (n+1) for _ in range(n+1)] for gap in range(1, n): for lo in range(1, n+1-gap): hi = lo + gap dp[lo][hi] = min(x + max(dp[lo][x-1], dp[x+1][hi]) for x in range(lo, hi)) return dp[1][n]

    public int getMoneyAmount(int n) {
        int[][] dp = new int[n+1][n+1];
        for (int L = n - 1; L > 0; L--) {
for (int R = L + 1; R <= n; R++) {
dp[L][R] = 0x7FFFFFFF; //INT_MAX
for (int i = L; i < R; i++) {
dp[L][R] = Math.min(dp[L][R], i + Math.max(dp[L][i - 1], dp[i + 1][R]));
}
}
}
return dp[1][n];
    }
https://discuss.leetcode.com/topic/51494/java-commented-dp-solution
Also, it takes a while for me to wrap my head around "min of max cost". My understand is that: you strategy is the best, but your luck is the worst. You only guess right when there is no possibilities to guess wrong.
public int getMoneyAmount(int n) {
    int[][] dp = new int[n+1][n+1];
    for(int len=1;len<n;len++){
        for(int i=1;i+len<=n;i++){
            int j=i+len;
            int min = Integer.MAX_VALUE;
            for(int k=i;k<j;k++){
              int tmp = k+Math.max(dp[i][k-1],dp[k+1][j]);
              min = Math.min(min,tmp);
            }
            dp[i][j] = min;
        }
    }
    return dp[1][n];
}
http://www.cnblogs.com/grandyang/p/5677550.html
这道题需要用到Minimax极小化极大算法,关于这个算法可以参见这篇讲解,并且题目中还说明了要用DP来做,那么我们需要建立一个二维的dp数组,其中dp[i][j]表示从数字i到j之间猜中任意一个数字最少需要花费的钱数,那么我们需要遍历每一段区间[j, i],维护一个全局最小值global_min变量,然后遍历该区间中的每一个数字,计算局部最大值local_max = k + max(dp[j][k - 1], dp[k + 1][i]),这个正好是将该区间在每一个位置都分为两段,然后取当前位置的花费加上左右两段中较大的花费之和为局部最大值,然后更新全局最小值,最后在更新dp[j][i]的时候看j和i是否是相邻的,相邻的话赋为i,否则赋为global_min
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for (int i = 2; i <= n; ++i) {
            for (int j = i - 1; j > 0; --j) {
                int global_min = INT_MAX;
                for (int k = j + 1; k < i; ++k) {
                    int local_max = k + max(dp[j][k - 1], dp[k + 1][i]);
                    global_min = min(global_min, local_max);
                }
                dp[j][i] = j + 1 == i ? j : global_min;
            }
        }
        return dp[1][n];
    }

记忆化搜索
http://fangde2.blogspot.com/2016/07/leetcode-q375-guess-number-higher-or.html
Definition of dp[i][j]: minimum number of money to guarantee win for subproblem [i, j].
Target: dp[1][n]
Corner case: dp[i][i] = 0 (because the only element must be correct)
Equation: we can choose k (i<=k<=j) as our guess, and pay price k. After our guess, the problem is divided into two subproblems. Notice we do not need to pay the money for both subproblems. We only need to pay the worst case (because the system will tell us which side we should go) to guarantee win. So dp[i][j] = min (i<=k<=j) { k + max(dp[i][k-1], dp[k+1][j]) }
int helper(int i, int j, vector<vector<int> >& myCache){
    if(i==j){
        myCache[i][j]=0;
        return 0;
    }
   
    if(myCache[i][j]!=-1)
        return myCache[i][j];
       
    myCache[i][j]=INT_MAX;
    for(int k = i; k<=j; k++){
        int l = k-1>=i? helper(i, k-1, myCache):0;
        int r = k+1<=j? helper(k+1, j, myCache):0;
        myCache[i][j] = min(myCache[i][j], k+max(l, r));
    }
   
    return myCache[i][j];
}

int getMoneyAmount(int n) {
    if(n==1)
        return 0;
       
    vector<vector<int> > myCache(n+1, vector<int> (n+1, -1));
    int res = helper(1, n, myCache);
    return res;
}

自顶向下(Top-down Approach)求解,采用辅助数组dp记录已经计算过的结果,减少重复计算。
def getMoneyAmount(self, n): """ :type n: int :rtype: int """ dp = [[0] * (n+1) for _ in range(n+1)] def solve(lo, hi): if lo < hi and dp[lo][hi] == 0: dp[lo][hi] = min(x + max(solve(lo,x-1), solve(x+1,hi)) for x in range(lo, hi)) return dp[lo][hi] return solve(1, n)



    public int getMoneyAmount(int n) {
        int[][] dp = new int[n+1][n+1];
        return solve(dp, 1, n);
    }
    int solve(int[][] dp, int L, int R) {
if (L >= R) return 0;
if (dp[L][R] != 0) return dp[L][R];
dp[L][R] = 0x7FFFFFFF;
for (int i = L; i <= R; i++) {
dp[L][R] = Math.min(dp[L][R], i + Math.max(solve(dp,L,i-1),solve(dp,i+1,R)));
}
return dp[L][R];

}
https://discuss.leetcode.com/topic/51353/simple-dp-solution-with-explanation
For each number x in range[i~j]
we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}
--> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.
then we get DP([i~j]) = min{xi, ... ,xj}
--> // this min makes sure that you are minimizing your cost.
public class Solution {
    public int getMoneyAmount(int n) {
        int[][] table = new int[n+1][n+1];
        return DP(table, 1, n);
    }
    
    int DP(int[][] t, int s, int e){
        if(s >= e) return 0;
        if(t[s][e] != 0) return t[s][e];
        int res = Integer.MAX_VALUE;
        for(int x=s; x<=e; x++){
            int tmp = x + Math.max(DP(t, s, x-1), DP(t, x+1, e));
            res = Math.min(res, tmp);
        }
        t[s][e] = res;
        return res;
    }
}
Here is a bottom up solution.
public class Solution {
    public int getMoneyAmount(int n) {
        int[][] table = new int[n+1][n+1];
        for(int j=2; j<=n; j++){
            for(int i=j-1; i>0; i--){
                int globalMin = Integer.MAX_VALUE;
                for(int k=i+1; k<j; k++){
                    int localMax = k + Math.max(table[i][k-1], table[k+1][j]);
                    globalMin = Math.min(globalMin, localMax);
                }
                table[i][j] = i+1==j?i:globalMin;
            }
        }
        return table[1][n];
    }
}
X.O(N^2)
https://discuss.leetcode.com/topic/51984/java-o-n-2-dp-solution-with-clear-explanation
The main idea of the algorithm is to optimize the computations for the trivial O(n^3) dp solution. My understanding for the algorithm is as follows. Notice that my code is a little different from the original code given by the two references.
First, define f[a][b] = the min worst-cast cost to guess a number a<=m<=b, thus, f[1][n] is the result, and f[a][b] = min{max{f[a][k-1], f[k+1][b]}+k} for a<=k<=b.
Second, define k0[a][b] = max{k : a<=k<=b && f[a][k-1]<=f[k+1][b]}. then
max{f[a][k-1], f[k+1][b]} = f[k+1][b] if a<=k<=k0[a][b], and =f[a][k-1] if k0[a][b]<k<=b.
Therefore, f[a][b]=min( f1[a][b], f2[a][b] ), where f1[a][b] = min{ f[k+1][b]+k } for a<=k<=k0[a][b], and f2[a][b] = min{ f[a][k-1]+k, k0[a][b]<k<=b} = f[a][k0[a][b]]+k0[a][b]+1.
Now the key is: given a, b, how to find k0[a][b] and f1[a][b], in O(1) time. And I think that is also the most tricky or difficult part.
We shall run the algorithm in double-looping structure, which is for(b=1, b<=n, b++){ for(a=b-1; a>0; a--) proceed_to_find_f[a][b]; }. Therefore, f[i][j] for abs(i-j)<b-a are already obtained, and k0[a+1][b] was just found.
Clearly, a<=k0[a][b]<=k0[a+1][b]<=b. Thus, along the inner loop of (a=b-1; a>0; a--), k0[all a's][b] would be found by definition in O(b) time. In other words, it is O(1) time to get k0[a][b] for fixed a, b.
Now consider the index sequence: a, a+1,..., k0[a][b] ,..., k0[a+1][b], ..., b.
Suppose currently a deque is used to store the values of { f[k+1][b]+k, a+1<=k<=k0[a+1][b] } sorted in ascending order (from the last step).
To find f1[a][b] = min{ f[k+1][b]+k } for a<=k<=k0[a][b], we have to throw away the values in the deque whose corresponding index j satisfies k0[a][b]<j<= k0[a+1][b], and add the value f[a+1][b]+a into deque, then extract the minimum. Since the deque is sorted, we can do the process by:
while(peekFirst().index > k0[a][b]) pollFirst();
while(f[a+1][b]+a < peekLast().value) pollLast(); // The elements polled are useless in the later loops (when a is smaller)
offerLast(new Item(index=a, value=f[a+1][b]+a));
f1[a][b] = peekFirst().value;
Similar to the insertion sort, the above process still yields a sorted deque. Notice that given a, b, the deque is offered only once. Thus, for fixed b, deque.size()<= b. Hence along the inner loop of (a=b-1;a>0; a--), deque is offered for b times, and so is polled at most for b times. In other words, it is O(1) time to get f1[a][b] for fixed a, b.
Since we have a double-looping with variables a,b, the overall time complexity is O(n^2). In fact, k0[ ][ ], f1[ ][ ], f2[ ][ ] needn't be stored
public int xxxgetMoneyAmount(int n) {
 int[][] f = new int[n + 1][n + 1];
 Deque<Integer[]> q; // item[]{index, value}

 int a, b, k0, v, f1, f2;

 for (b = 2; b <= n; b++) {
  k0 = b - 1;
  q = new LinkedList<Integer[]>();

  for (a = b - 1; a > 0; a--) {
   // find k0[a][b] by definition in O(1) time.
   while (f[a][k0 - 1] > f[k0 + 1][b])
    k0--;

   // find f1[a][b] in O(1) time.
   while (!q.isEmpty() && q.peekFirst()[0] > k0)
    q.pollFirst();

   v = f[a + 1][b] + a;

   while (!q.isEmpty() && v < q.peekLast()[1])
    q.pollLast();

   q.offerLast(new Integer[] { a, v });

   f1 = q.peekFirst()[1];
   f2 = f[a][k0] + k0 + 1;
   f[a][b] = Math.min(f1, f2);
  }
 }

 return f[1][n];
}
Notice that the operations of deques are not quite efficient. However, from the analysis above, we know that deque.size()<= b, therefore,we can just use arrays of size O(n) to fulfill the operations of the deque. The code is as follows, which runs about 4 times faster than the one above.
public int getMoneyAmount(int n) {
 int[][] f = new int[n + 1][n + 1];

 // replace deque by idx and val arrays:
 // q.pollFirst()={index[beginIdx], value[beginIdx]},
 // q.pollLast()={index[endIdx], value[endIdx]}, ...
 int beginIdx, endIdx;
 int[] index = new int[n + 1];
 int[] value = new int[n + 1];

 int a, b, k0, v, f1, f2;

 for (b = 2; b <= n; b++) {
  k0 = b - 1;

  beginIdx = 0;
  endIdx = -1; // q.isEmpty()==(beginIdx>endIdx)

  for (a = b - 1; a > 0; a--) {
   // find k0[a][b] by definition in O(1) time.
   while (f[a][k0 - 1] > f[k0 + 1][b])
    k0--;

   // find f1[a][b] in O(1) time.
   while (beginIdx <= endIdx && index[beginIdx] > k0)
    beginIdx++; // q.pollFirst();

   v = f[a + 1][b] + a;

   while (beginIdx <= endIdx && v < value[endIdx])
    endIdx--; // q.pollLast();

                        // q.offerLast(new Integer[] { a, v });
   endIdx++;
   index[endIdx] = a;
   value[endIdx] = v; 

   f1 = value[beginIdx];
   f2 = f[a][k0] + k0 + 1;
   f[a][b] = Math.min(f1, f2);
  }
 }

 return f[1][n];
}
https://discuss.leetcode.com/topic/51487/an-o-n-2-dp-solution-quite-hard
http://artofproblemsolving.com/community/c296841h1273742
First, here is a trivial DP solution with $O(n^{3})$. Let $f(a,b)$ be the minimum worst-case cost to guess a number $a\le n\le b$, then we have$$
f(a,b)=\min_{a\le k\le b}\Big(\max\big\{ f(a,k-1),f(k+1,b)\big\}+k\Big)\ .
$$Enumerate $k$ and we are done. To optimize the computation, let$$
k_{0}(a,b)=\max\{k:f(a,k-1)\le f(k+1,b)\}\ ,
$$then\begin{align*}
 & \max\big\{ f(a,k-1),f(k+1,b)\big\}\\
= & \begin{cases}
f(k+1,b) & \text{if }a\le k\le k_{0}(a,b)\\
f(a,k-1) & \text{if }k_{0}(a,b)<k\le b
\end{cases}\;.
\end{align*}Therefore,\begin{align*}
f(a,b) & =\min\big\{ f_{1}(a,b),f_{2}(a,b)\big\}\\
f_{1}(a,b) & =\min_{a\le k\le k_{0}(a,b)}\big(f(k+1,b)+k\big)\\
f_{2}(a,b) & =\min_{k_{0}(a,b)<k\le b}\big(f(a,k-1)+k\big)\\
 & =f\big(a,k_{0}(a,b)\big)+k_{0}(a,b)+1\ .
\end{align*}Notice that $k_{0}(a_{1},b)\le k_{0}(a_{2},b)$ when $a_{1}\le a_{2}$. So we can compute $k_{0}(a,b)$ in amortized $O(1)$ time. Then we need the sliding minimum of $g(k,b)=f(k+1,b)+k$ with $b$ fixed and $a\le k\le k_{0}(a,b)$. This can be done using an increasing deque, and it takes amortized $O(1)$ time to get the desired minimum. We need to compute $O(n^{2})$ values of $f$, and each takes $O(1)$ time, so in all $O(n^{2})$.
    int getMoneyAmount(int n) {
        vector<vector<int>> u(n + 2, vector<int>(n + 2));
        for (int b = 2; b <= n; ++b) {
            int k0 = b - 1;
            deque<pair<int, int>> v;
            for (int a = b - 1; a; --a) {
                while (u[a][k0 - 1] > u[k0 + 1][b]) {
                    if (!v.empty() && v.front().second == k0) v.pop_front();
                    --k0;
                }
                int vn = a + u[a + 1][b];
                while (!v.empty() && vn < v.back().first) v.pop_back();
                v.emplace_back(vn, a);
                int u1 = u[a][k0] + k0 + 1;
                int u2 = v.front().first;
                u[a][b] = u1 < u2 ? u1 : u2;
            }
        }
        return u[1][n];
    }

我们可以将路径打印出来,来看看具体的选择策略的过程,以便加深理解
https://discuss.leetcode.com/topic/52760/still-confused-about-guarantee-a-win-why-minimize-the-max-cost/2
When n = 10, the answer is 16 by any of the correct solutions here. However, the example in the question clearly gives a scenario that you have to pay 21 to win the game. If you only have 16, how is it possible to guarantee a win?
I see a post said this problem is essentially "Best strategy and worst luck". However, assume there is a person coming into play, how is it possible that he knows the best strategy? If not, he is very likely to make some bad moves. If a win needs to be guaranteed, then should we consider the "worst strategy"?
So my question is, why each time we minimize the max cost?
The example in the problem description was intended to demonstrate the rules of the game. It does not reflect the optimal strategy.
The problem is to find a strategy that minimizes the cost for any possible secret number in [1..N]. If a player adheres to that strategy, it will be impossible for them to lose more than this minimum.
You can visualize the strategy as a binary tree. For N = 10:
0_1469924346187_strategy10.png
The secret number can be any number [1..10] but if you choose your sequence of guesses by following the left or right branches according to whether your guess was high or low, then you will always guess the right number while losing no more than $16.



No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (639) to-do (598) Review (343) Classic Algorithm (334) Classic Interview (299) Dynamic Programming (263) Google Interview (233) LeetCode - Review (229) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) List (58) Binary Tree (56) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Interval (38) Jobdu (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) Trie (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Suffix Tree (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Kadane’s Algorithm (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts