Thursday, July 28, 2016

Not So Random - Round-E APAC Test of Google 2016 (Problem C)


http://www.dss886.com/algorithm/2016/05/18/21-36
There is a certain “random number generator” (RNG) which takes one nonnegative integer as input and generates another nonnegative integer as output. But you know that the RNG is really not very random at all! It uses a fixed number K, and always performs one of the following three operations:
  • with probability A/100: return the bitwise AND of the input and K
  • with probability B/100: return the bitwise OR of the input and K
  • with probability C/100: return the bitwise XOR of the input and K (You may assume that the RNG is truly random in the way that it chooses the operation each time, based on the values of A, B, and C.)
You have N copies of this RNG, and you have arranged them in series such that output from one machine will be the input for the next machine in the series. If > you provide X as an input to the first machine, what will be the expected value of the output of the final machine in the series?
Input
The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with six integers N, X, K, A, B, and C. Respectively, these denote the number of machines, the initial input, the fixed number with which all the bitwise operations will be performed (on every machine), and 100 times the probabilities of the bitwise AND, OR, and XOR operations.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the expected value of the final output. y will be considered correct if it is within an absolute or relative error of 10^-9 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
Limits
1 ≤ T ≤ 50.
0 ≤ A ≤ 100.
0 ≤ B ≤ 100.
0 ≤ C ≤ 100.
A+B+C = 100.
Small dataset
1 ≤ N ≤ 10.
0 ≤ X ≤ 10^4.
0 ≤ K ≤ 10^4.
Large dataset
1 ≤ N ≤ 10^5.
0 ≤ X ≤ 10^9.
0 ≤ K ≤ 10^9.
Sample
InputOutput
3 
1 5 5 10 50 40Case #1: 3.0000000000
2 5 5 10 50 40Case #2: 3.6000000000
10 15 21 70 20 10Case #3: 15.6850579098
In sample test case #1, the final output will be 5 if AND or OR happens and 0 if XOR happens. So the probability of getting 5 is (0.1 + 0.5) and the probability of getting 0 is 0.4. So the expected final output is 5 * 0.6 + 0 * 0.4 = 3.
In sample test case #2, the final output will be 5 with probability 0.72, and 0 otherwise.

首先理一下题意,把N个RNG串起来,求最后输出结果的期望值。这里很容易注意到,RNG内部的操作(与、或、异或)都是位运算,而一个二进制整数的期望可以用每一位比特的期望乘以所在位的权重计算得到,那么本题就可以简化为只考虑单个比特在系统内的流程来得到单个比特位的期望值。

单个RNG

只考虑一个bit的话,X和K的值组合只有4种,可以列出下面的操作结果表:
ABC
 0 & 0 = 0  0 | 0 = 0  0 ^ 0 = 0 
 0 & 1 = 0  0 | 0 = 1  0 ^ 1 = 1 
 1 & 0 = 0  0 | 0 = 1  1 ^ 0 = 1 
 1 & 1 = 1  1 | 1 = 1  1 ^ 1 = 0 
注意到这里虽然有A、B、C三种可能性,但是输入和输出都是0和1,是不是可以尝试一下用转移矩阵来做呢?
因为输入是X、输出是0或1,而K是相对固定的、每个RNG的K值都相同。因此,对照上面的结果表分别计算K=0和K=1时的转移矩阵:
k = 0:
[ 100 ,  0 ]
[ A , B+C ]
k = 1:
[ A , B + C ]
[ C , A + B ]
(即k=1,输入为0时,输出A%为0、(B+C)%为1;输入为1时,输出C%为0,(A+B)%为1)
这样,我们就将RNG内部当作了一个黑箱,将内部的三种操作简化成了输入输出的转移矩阵。

多个RNG串联

有了单个RNG的转移矩阵,K值又不变,就可以分别计算K=0和K=1时多个RNG的串联结果了,将N-1个矩阵相乘即可。

https://github.com/dss886/LeetCode/blob/master/src/company/google/NotSoRandom.java
* From the Round-E APAC Test of Google 2016 (Problem C)
* https://code.google.com/codejam/contest/8264486/dashboard#s=p2
*
* The main solving ideas:
* 1. All Three operation is bit-based, so we can look into the operation of single bit.
* 2. Instead of considering the 3 operations and their probabilities, we can just think about the input and output
*    probability of 0-1, then we got two matrices as below:
*        k = 0: [ 100 ,  0   ] , k = 1: [  A  , B + C ]
*               [  A  , B+C  ]          [  C  , A + B ]
*    (which means: when x=0 and k=1, the output got 0 by chance of A%, and 1 by chance of (B+C)%)
* 3. When have N copies of this RNG in series, we multiply the matrices to itself by N-1 times, then we got the total
*    system's output matrices.
* 4. Now for every bit of X and K, we can calculate the output bit chance from the matrices above, then we can finally
*    got the result.
*
* For example:
*    N=1, X=5, K=5, A=10, B=50, C=40, the single and total matrices (N=1) is:
*        k = 0: [ 100 ,  0  ] , k = 1: [  10  , 90 ]
*               [ 10  , 90  ]          [  40  , 60 ]
*    X = 00000000000000000000000000000101
*    K = 00000000000000000000000000000101
*    1. when bit of X and K are both 0, the output bit is 0 by 100%.
*    2. when bit of X and K are both 1, the output bit is 0 by 40% and 1 by 60%.
*    So the expect value of result is (60% * 4 + 60% * 1), which is 3.
*
* For Improvement:
*   The main time-consuming part of this solution is the multiplication of matrices.
*   Some fast matrix multiplication like the Strassen-Algorithm will reduce the consumed time.
*/
public class NotSoRandom {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       while (scanner.hasNext()) {
           int T = scanner.nextInt();
           for (int t = 0; t < T; t++) {
               int N = scanner.nextInt();
               int X = scanner.nextInt();
               int K = scanner.nextInt();
               int A = scanner.nextInt();
               int B = scanner.nextInt();
               int C = scanner.nextInt();
               Matrix bitZero = new Matrix(100, 0, A, B + C);
               Matrix bitOne = new Matrix(A, B + C, C, A + B);
               Matrix bitZeroAfterK = bitZero;
               Matrix bitOneAfterK = bitOne;
               for (int n = 1; n < N; n++) {   // Maybe some Fast-Matrix-Multiplication will do it faster.
                   bitZeroAfterK = multiply(bitZeroAfterK, bitZero);
                   bitOneAfterK = multiply(bitOneAfterK, bitOne);
               }
               double result = 0;
               for (int i = 31; i >= 0; i--) {
                   result *= 2;
                   Matrix matrix = isLastZero(K, i) ? bitZeroAfterK : bitOneAfterK;
                   double chanceOfOne = (isLastZero(X, i) ? matrix.b : matrix.d) / 100;
                   result += chanceOfOne;
               }
               print(t, result);
           }
       }
   }

   private static boolean isLastZero(int num, int position) {
       return (num >>> position) % 2 == 0;
   }

   private static void print(int t, double result) {
       System.out.println("Case #" + (t + 1) + ": " + result);
   }

   private static Matrix multiply(Matrix m1, Matrix m2) {
       double a = (m1.a * m2.a + m1.b * m2.c) / 100;
       double b = (m1.a * m2.b + m1.b * m2.d) / 100;
       double c = (m1.c * m2.a + m1.d * m2.c) / 100;
       double d = (m1.c * m2.b + m1.d * m2.d) / 100;
       return new Matrix(a, b, c, d);
   }

   private static class Matrix {
       private double a, b, c, d;
       public Matrix(double a, double b, double c, double d) {
           this.a = a;
           this.b = b;
           this.c = c;
           this.d = d;
       }
   }

http://goudan-er.xyz/2016/Google-APAC-2016-RoundE-Problem-C/
对于数字二进制下的每一位只有两种状态0或者1,同时每一位相互独立,所以可以分开考虑每一位,就算出经过N步之后每一位为1的概率,则最后的期望可以表示为:expect=j=031pj(1«j) ,pj表示经过N步随机数字生成函数后第j位为1的概率。
所以,有DP:
令dp[i][j][s]表示经过i步随机数字生成函数后第j位状态为s的概率,s = 0 / 1,有状态转移方程:
If (k & (1 << j)) > 0 :
dp[i][j][0] += dp[i-1][j][0] * a / 100
dp[i][j][0] += dp[i-1][j][1] * c / 100
dp[i][j][1] += dp[i-1][j][1] * a / 100
dp[i][j][1] += dp[i-1][j][0] * b / 100
dp[i][j][1] += dp[i-1][j][1] * b / 100
dp[i][j][1] += dp[i-1][j][0] * c / 100
Else :
dp[i][j][0] += dp[i-1][j][0] * a / 100
dp[i][j][0] += dp[i-1][j][1] * a / 100
dp[i][j][0] += dp[i-1][j][0] * b / 100
dp[i][j][0] += dp[i-1][j][0] * c / 100
dp[i][j][1] += dp[i-1][j][1] * b / 100
dp[i][j][1] += dp[i-1][j][1] * c / 100
初始化,则根据X的每一位0或者1,对dp[0][j][0]和dp[0][j][1]赋值1或者0。
typedef long long lld;
 
const int N = 111111;
const int M = 31; // x & k >= 0, bit(31) = 0
 
double dp[N][M][2];
 
double solve()
{
    double ret = 0.0;
    int n, x, k, a, b, c;
    cin >> n >> x >> k >> a >> b >> c;
 
    // init
    clr(dp, 0);
    for (int j = 0; j < M; ++j) {
        if ( x & (1 << j) ) {
            dp[0][j][0] = 0.0;
            dp[0][j][1] = 1.0;
        } else {
            dp[0][j][0] = 1.0;
            dp[0][j][1] = 0.0;
        }
    }
 
    // dp
    for (int j = 0; j < M; ++j) {
        for (int i = 1; i <= n; ++i) {
            if ( k & (1 << j) ) {
                dp[i][j][0] += dp[i-1][j][0] * a / 100;
                dp[i][j][0] += dp[i-1][j][1] * c / 100;
                dp[i][j][1] += dp[i-1][j][1] * a / 100;
                dp[i][j][1] += (dp[i-1][j][0] + dp[i-1][j][1]) * b / 100;
                dp[i][j][1] += dp[i-1][j][0] * c / 100;
            } else {
                dp[i][j][0] += (dp[i-1][j][0] + dp[i-1][j][1]) * a / 100;
                dp[i][j][0] += dp[i-1][j][0] * b / 100;
                dp[i][j][0] += dp[i-1][j][0] * c / 100;
                dp[i][j][1] += dp[i-1][j][1] * b / 100;
                dp[i][j][1] += dp[i-1][j][1] * c / 100;
            }
        }
        ret += dp[n][j][1] * (1 << j);
    }
 
    return ret;
}
 
int main ()
{
    freopen("F:/#test-data/in.txt", "r", stdin);
    freopen("F:/#test-data/out.txt", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0);
    cout << fixed << showpoint;
    int t; cin >> t;
    for (int cas = 1; cas <= t; ++cas) {
        cout << "Case #" << cas << ": ";
        cout << setprecision(9) << solve() << endl;
    }
    return 0;
}
http://blog.csdn.net/ww32zz/article/details/51362183
题目大意:对于一个“随机数生成器”,给定,输出的结果可能有三种,①  ② ③。求重复操作次,最后得到的结果的期望值。
思路:首先理解求的是什么——期望,即:。所以要求解问题,就要知道有哪些可能的取值,并计算其概率。但是可能的取值太多,计算概率也很麻烦,所以要寻找突破口——位运算。因为提供的运算都是位运算:按位与、按位或、按位异或,并且每一个bit都是相互独立的。因此第一反应应该是将问题分解为逐位求期望。则问题转化为:。所以我们只需要求每一个bit贡献的期望,然后累加到结果中就行了。
有了以上思路,接下来就是怎么求解某个bit的期望了。不失一般性,以下对第位进行分析。在整个运算中,是不变的,来一个输入变量,可以很快求出结果为0、为1的概率。如下:
有了上述一轮运算的状态迁移后,我们可以写出状态的递推关系:
 
由此可得状态转移矩阵:
对给定的输入,初始概率可以根据bit为0或者为1求得,进行轮则对状态转移矩阵求次幂即可,使用快速幂复杂度为


总结:首先要理解题意,将要解决的原始问题想清楚,再从算法的角度去考虑问题。对于有限的状态转换,可以使用状态转移矩阵来表示,然后将重复的操作转换成矩阵连乘,还可以使用快速幂进行优化。

  1. void multiply(double m1[], double m2[]){  
  2.     double ans[] = {0, 0, 0, 0};  
  3.     ans[0] = m1[0] * m2[0] + m1[1] * m2[2];  
  4.     ans[1] = m1[0] * m2[1] + m1[1] * m2[3];  
  5.     ans[2] = m1[2] * m2[0] + m1[3] * m2[2];  
  6.     ans[3] = m1[2] * m2[1] + m1[3] * m2[3];  
  7.     for(int i = 0; i < 4; ++i)  
  8.         m1[i] = ans[i];  
  9. }  
  10.   
  11. int main(){  
  12.     int tc, ca = 0;  
  13.     cin >> tc;  
  14.     while(tc--){  
  15.         int n, x, k;  
  16.         double a, b, c;  
  17.         cin >> n >> x >> k >> a >> b >> c;  
  18.         a /= 100, b /= 100, c /= 100;  
  19.         /*ans0,ans1保存最终的状态*/  
  20.         double ans0[] = {1, 0, 0, 1}, ans1[] = {1, 0, 0, 1};  
  21.         double cur0[] = {1, a, 0, b + c}, cur1[] = {a, c, b + c, a + b};  
  22.         while(n){  
  23.             if(n & 1)  
  24.                 multiply(ans0, cur0), multiply(ans1, cur1);  
  25.             multiply(cur0, cur0), multiply(cur1, cur1);  
  26.             n >>= 1;  
  27.         }  
  28.         /*按位求期望*/  
  29.         int base = 1;  
  30.         double res = 0;  
  31.         while(x || k){  
  32.             /*p0,p1表示初始状态为0,1的概率,c0,c1表示相应的矩阵系数*/  
  33.             double p1 = x & 1 ? 1 : 0, p0 = 1 - p1;  
  34.             double c0, c1;  
  35.             if(k & 1)  
  36.                 c0 = ans1[2], c1 = ans1[3];  
  37.             else  
  38.                 c0 = ans0[2], c1 = ans0[3];  
  39.             res += (c0 * p0 + c1 * p1) * base;  //求解当前bit的期望  
  40.             base <<= 1, x >>= 1, k >>= 1;  
  41.         }  
  42.         printf("Case #%d: %.10lf\n", ++ca, res);  
  43.     }  
  44. }  


No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (637) to-do (598) Review (340) Classic Algorithm (334) Classic Interview (299) Dynamic Programming (263) Google Interview (234) 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) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (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