Saturday, October 15, 2016

LeetCode 421 - Maximum XOR of Two Numbers in an Array


https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].
Could you do this in O(n) runtime?

Input: [3, 10, 5, 25, 2, 8]
Output: 28

X.  http://bookshadow.com/weblog/2016/10/15/leetcode-maximum-xor-of-two-numbers-in-an-array/
解法I 分治法(Divide and Conquer)+ 位运算(Bit Manipulation)
求数组中两两数字的异或运算的最大值,朴素的解法是O(n ^ 2),不满足题目要求。
异或运算(XOR)的实质是“同零异一”。
题目描述中a[i]的范围[0, 2^32),至多有32位,因此可以通过位运算处理。
递归函数定义为:solve(nums0, nums1, mask)。

令mask从最高位(1<<31)向最低位(1)逐步右移,将数组nums按照如下规则分成两部分:

nums中,与mask按位与结果为0的所有数字,记为nums0

nums中,与mask按位与结果为1的所有数字,记为nums1

如果nums0与nums1其一为空,说明nums中所有数字在该二进制位同0或同1,其异或结果一定为0

如果nums0与nums1均不为空,说明nums中的数字在该位的异或值为1,令mask右移一位,再将nums0与nums1进一步划分成四部分:

nums0中,与mask按位与结果为0的所有数字,记为nums00

nums0中,与mask按位与结果为1的所有数字,记为nums01

nums1中,与mask按位与结果为0的所有数字,记为nums10

nums1中,与mask按位与结果为1的所有数字,记为nums11

分支1:如果nums00与nums11同时存在,递归求解solve(nums00, nums11, mask)的结果

分支2:如果nums01与nums10同时存在,递归求解solve(nums01, nums10, mask)的结果

从上述两个分支中求最大值ans

若ans为0,说明上述两分支均不存在,nums中mask对应二进制位的所有数字同0或者同1,此时计算分支3

分支3:递归计算solve(nums0, nums1, mask) - mask

最后将结果+mask * 2,并返回
def findMaximumXOR(self, nums): """ :type nums: List[int] :rtype: int """ def solve(nums0, nums1, mask): if mask <= 1: return mask mask /= 2 nums01 = [n for n in nums0 if n & mask] nums00 = [n for n in nums0 if not n & mask] nums11 = [n for n in nums1 if n & mask] nums10 = [n for n in nums1 if not n & mask] ans = 0 if nums10 and nums01: ans = max(ans, solve(nums10, nums01, mask)) if nums00 and nums11: ans = max(ans, solve(nums00, nums11, mask)) if not ans: ans = solve(nums0, nums1, mask) - mask return ans + mask * 2 mask = 1 << 31 while mask: nums0 = [n for n in nums if not n & mask] nums1 = [n for n in nums if n & mask] if nums0 and nums1: break mask >>= 1 return solve(nums0, nums1, mask)
http://www.cnblogs.com/grandyang/p/5991530.html
按位遍历,题目中给定了数字的返回不会超过231,那么最多只能有32位,我们用一个从左往右的mask,用来提取数字的前缀,然后将其都存入set中,我们用一个变量t,用来验证当前位为1再或上之前结果res,看结果和set中的前缀异或之后在不在set中,这里用到了一个性质,若a^b=c,那么a=b^c,因为t是我们要验证的当前最大值,所以我们遍历set中的数时,和t异或后的结果仍在set中,说明两个前缀可以异或出t的值,所以我们更新res为t,继续遍历,如果上述讲解不容易理解,那么建议自己带个例子一步一步试试,并把每次循环中set中所有的数字都打印出来,基本应该就能理解了
http://blog.csdn.net/mebiuw/article/details/52901057
不过两个解法的核心都是: 
a^b = c ->a^c=b,b^c=a 
// a^b = c ->a^c=b,b^c=a public int findMaximumXOR(int[] nums) { int max = 0, mask = 0; for(int i = 31; i >= 0; i--){ //mask从0x01 ->0x03等一直变化,取后i位 mask = mask | (1 << i); Set<Integer> set = new HashSet<>(); for(int num : nums){ set.add(num & mask); } //tmp表示当前的最大 int tmp = max | (1 << i); System.out.println(mask+" "+tmp+" "+max); for(int prefix : set){ //证明存在一个数使得tmp^x = prefix if(set.contains(tmp ^ prefix)) { max = tmp; break; } } } return max; }
https://segmentfault.com/a/1190000007283296
利用XOR的性质,a^b = c, 则有 a^c = b,且 b^c = a;
所以每次从高位开始,到某一位为止,所能获得的最大的数。设置变量mask用来表示能形成的值,每一次将mask和其他的num相与得到的值加入set,表示在当前这一位上,数组里有这么多prefix。
假定在某一位上的任意两数xor能得到的最大值是tmp,那么他一定满足a(xor)b = tmp,其中set.contains(a) && set.contains(b). 所以,我们只需要判断b(xor)tmp的结果是不是在当前这一位下的set内,就可以知道这个tmp能不能又这个set中的任意两个数组成。
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        // test each bit pose, 判断能不能构成所需要的值;
        for(int i = 31; i >= 0; i --) {
            // 每次都在之前的基础上更新mask
            mask = mask | (1 << i);
            Set<Integer> set = new HashSet<>();
            for(int num : nums) {
                // add the number which has the mask as its prefix;
                set.add(num & mask);
            }
            // 假设当前所能达到的最大值是这个temp值;
            int tmp = max | (1 << i);
            for(Integer prefix : set) {
                if(set.contains(prefix ^ tmp)) {
                    // 如果能组成就直接break 
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }
http://hankerzheng.com/blog/LeetCode-Maximum-XOR-of-Two-Numbers-in-an-Array
利用异或的特性, 这题可以有更好的解法. 对于异或运算, 我们有
如果a ^ b = c, 那么a ^ c = b.
根据这个定理, 我们从最高位开始找, 我们先将所有数的最高位存到一个Set中. 然后, 我们假设最终答案的最高位为1, 将数列中所有数的最高位和1进行异或运算, 异或得到的结果仍然在Set中, 那么说明最终答案的最高位一定为1, (由定理可得1 ^ x = b <==> b ^ x = 1, 对与数x, 一定存在一个数b, 使得x ^ b = 1), 否则最高位的答案一定为0.
假设我们已经知道最终答案的最高k位为prefix, 我们先将数列中所有数的最高k+1位存入Set中. 然后, 我们假设下一位的值为1, 将数列中所有数的最高k+1位与prefix*2 + 1进行异或运算, 如果异或得到的结果仍然在Set中, 那么说明最终答案的第k+1位一定为1, 否则, 最高位的答案一定为0.
因为x ^ (prefix*2+1) = b <==> x ^ b = prefix*2+1, 即对于数x, 一定存在一个数b, 使得他们异或的结果为prefix*2+1.
因此, 我们可以对最终答案的32位进行依次判断, 最终得到异或的最大值.
该算法的时间复杂度为O(32n) = O(n).

X.
解法II Set数据结构 + 位运算
https://discuss.leetcode.com/topic/63299/python-6-lines-bit-by-bit/2
Build the answer bit by bit from left to right. Let's say we already know the largest first seven bits we can create. How to find the largest first eight bits we can create? Well it's that maximal seven-bits prefix followed by 0 or 1. Append 0 and then try to create the 1 one (i.e., answer ^ 1) from two eight-bits prefixes from nums. If we can, then change that 0 to 1.
    int findMaximumXOR(vector<int>& nums) {
        int res = 0;
        unordered_set<int> pre;
        for (int i = 31; i >= 0; i--) {
            res <<= 1;
            pre.clear();
            for (auto n : nums) 
                pre.insert(n >> i);
            for (auto p : pre)
                if (pre.find((res ^ 1) ^ p) != pre.end()) {
                    res++;
                    break;
                }
        }
        return res;
    }
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
example: Given [14, 11, 7, 2], which in binary are [1110, 1011, 0111, 0010].
Since the MSB is 3, I'll start from i = 3 to make it simplify.
  1. i = 3, set = {1000, 0000}, max = 1000
  2. i = 2, set = {1100, 1000, 0100, 0000}, max = 1100
  3. i = 1, set = {1110, 1010, 0110, 0010}, max = 1100
  4. i = 0, set = {1110, 1011, 0111, 0010}, max = 1100
The mask is 1000, 1100, 1110, 1111.
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            HashSet<Integer> set = new HashSet<Integer>();
            for (int num : nums) {
                set.add(num & mask); // reserve Left bits and ignore Right bits
            }
            
            /* Use 0 to keep the bit, 1 to find XOR
             * 0 ^ 0 = 0 
             * 0 ^ 1 = 1
             * 1 ^ 0 = 1
             * 1 ^ 1 = 0
             */
            int tmp = max | (1 << i); // in each iteration, there are pair(s) whoes Left bits can XOR to max
            for (int prefix : set) {
                if (set.contains(tmp ^ prefix)) {
                    max = tmp;
                }
            }
        }
        return max;
    }
I saw deeply and found out a very important xor feature I missed, that is: if a^b=c, then a^c=b, b^c=a. That's why the answer using this code:
            for(int prefix : set){
                if(set.contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
Agreed. Actually, this is the most important operation that made this code linear. Instead of choosing 2 from n, we verify if we can achieve maximum value -- 1 -- on each bit reversely based on the feature you have mentioned
to iteratively determine what would be each bit of the final result from left to right. And it narrows down the candidate group iteration by iteration. e.g. assume input are a,b,c,d,...z, 26 integers in total. In first iteration, if you found that a, d, e, h, u differs on the MSB(most significant bit), so you are sure your final result's MSB is set. Now in second iteration, you try to see if among a, d, e, h, u there are at least two numbers make the 2nd MSB differs, if yes, then definitely, the 2nd MSB will be set in the final result. And maybe at this point the candidate group shinks from a,d,e,h,u to a, e, h. Implicitly, every iteration, you are narrowing down the candidate group, but you don't need to track how the group is shrinking, you only cares about the final result.
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for(int i = 31; i >= 0; i--){
            mask = mask | (1 << i);
            Set<Integer> set = new HashSet<>();
            for(int num : nums){
                set.add(num & mask);
            }
            int tmp = max | (1 << i);
            for(int prefix : set){
                if(set.contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }
解法III 字典树(Trie) + 位运算
https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
    class Trie {
        Trie[] children;
        public Trie() {
            children = new Trie[2];
        }
    }
    
    public int findMaximumXOR(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        // Init Trie.
        Trie root = new Trie();
        for(int num: nums) {
            Trie curNode = root;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >>> i) & 1;
                if(curNode.children[curBit] == null) {
                    curNode.children[curBit] = new Trie();
                }
                curNode = curNode.children[curBit];
            }
        }
        int max = Integer.MIN_VALUE;
        for(int num: nums) {
            Trie curNode = root;
            int curSum = 0;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >>> i) & 1;
                if(curNode.children[curBit ^ 1] != null) {
                    curSum += (1 << i);
                    curNode = curNode.children[curBit ^ 1];
                }else {
                    curNode = curNode.children[curBit];
                }
            }
            max = Math.max(curSum, max);
        }
        return max;
    }
It gets me TLE as well. Ditching the Trie class and just using Object[] gets it accepted in about 185 ms:
    public int findMaximumXOR(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        // Init Trie.
        Object[] root = {null, null};
        for(int num: nums) {
            Object[] curNode = root;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >>> i) & 1;
                if(curNode[curBit] == null) {
                    curNode[curBit] = new Object[]{null, null};
                }
                curNode = (Object[]) curNode[curBit];
            }
        }
        int max = Integer.MIN_VALUE;
        for(int num: nums) {
            Object[] curNode = root;
            int curSum = 0;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >>> i) & 1;
                if(curNode[curBit ^ 1] != null) {
                    curSum += (1 << i);
                    curNode = (Object[]) curNode[curBit ^ 1];
                }else {
                    curNode = (Object[]) curNode[curBit];
                }
            }
            max = Math.max(curSum, max);
        }
        return max;
    }
https://discuss.leetcode.com/topic/64753/31ms-o-n-java-solution-using-trie
We add the number into the trie and find the max possible XOR result at the same time.
Node.set() method will set the new node in the trie if needed and return the new node.
After setting the node, find the opposite bit in the trie to maximize the possible XOR result.
    public class Node {
        Node one;
        Node zero;
        Node() {
            this.one = null;
            this.zero = null;
        }
        Node set(int n) {
            if (n == 0) {
                if (this.one == null) this.one = new Node();
                return this.one;
            }
            if (this.zero == null) this.zero = new Node();
            return this.zero;
        }
    }
    
    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        int re = 0;
        for (int num : nums) {
            int digit = num;
            int tmp = 0;
            Node setNode = root;
            Node findNode = root;
            int pos = 30;
            while (pos >= 0) {
                digit = (num >> pos) & 1;
                setNode = setNode.set(digit);
                if (digit == 1) {
                    if (findNode.one != null) {
                        tmp = tmp | (1 << pos);
                        findNode = findNode.one;
                    } else {
                        findNode = findNode.zero;
                    }
                } else {
                    if (findNode.zero != null) {
                        tmp = tmp | (1 << pos);
                        findNode = findNode.zero;
                    } else {
                        findNode = findNode.one;
                    }
                }
                pos--;
            }
            re = Math.max(re, tmp);
        }
        return re;
    }

TODO
https://discuss.leetcode.com/topic/64431/a-solution-based-on-bartoszkp-s-with-missing-test-cases
https://discuss.leetcode.com/topic/63759/c-o-nlogk-solution-with-ordering-bits-with-o-logk-additional-memory-for-recursion-stack

http://www.1point3acres.com/bbs/thread-202685-3-1.html

http://www.geeksforgeeks.org/minimum-xor-value-pair/
Given an array of integers. Find the pair in an array which has minimum XOR value

int minXOR(int arr[], int n)
{
    int min_xor = INT_MAX; // Initialize result
    // Generate all pair of given array
    for (int i=0; i < n; i++)
        for (int j=i+1; j<n; j++)
            // update minimum xor value if required
            min_xor = min(min_xor, arr[i] ^ arr[j] );
    return min_xor;
}

An Efficient solution can solve the above problem in O(n) time under the assumption that integers take fixed number of bits to store. The idea is to use Trie Data Structure. Below is algorithm.
1). Create an empty trie. Every node of trie contains two children
    for 0 and 1 bits.
2). Initialize min_xor = INT_MAX, insert arr[0] into trie
3). Traversal all array element one-by-one starting from second.
     a. First find minimum setbet difference value in trie 
        do xor of current element with minimum setbit diff that value 
     b. update min_xor value if required
     c. insert current array element in trie 
4). return min_xor
struct TrieNode
{
    int value; // used in leaf node
    TrieNode * Child[2];
};
// Utility function to create a new Trie node
TrieNode * getNode()
{
    TrieNode * newNode = new TrieNode;
    newNode->value = 0;
    newNode->Child[0] = newNode->Child[1] = NULL;
    return newNode;
}
// utility function insert new key in trie
void insert(TrieNode *root, int key)
{
    TrieNode *temp = root;
    // start from the most significant bit , insert all
    // bit of key one-by-one into trie
    for (int i = INT_SIZE-1; i >= 0; i--)
    {
        // Find current bit in given prefix
        bool current_bit = (key & (1<<i));
        // Add a new Node into trie
        if (temp->Child[current_bit] == NULL)
            temp->Child[current_bit] = getNode();
        temp = temp->Child[current_bit];
    }
    // store value at leafNode
    temp->value = key ;
}
// Returns minimum XOR value of an integer inserted
// in Trie and given key.
int  minXORUtil(TrieNode * root, int key)
{
    TrieNode * temp = root;
    for (int i=INT_SIZE-1; i >= 0; i--)
    {
        // Find current bit in given prefix
        bool current_bit = ( key & ( 1<<i) );
        // Traversal Trie, look for prefix that has
        // same bit
        if (temp->Child[current_bit] != NULL)
            temp = temp->Child[current_bit];
        // if there is no same bit.then looking for
        // opposite bit
        else if(temp->Child[1-current_bit] !=NULL)
            temp = temp->Child[1-current_bit];
    }
    // return xor value of minimum bit difference value
    // so we get minimum xor value
    return key ^ temp->value;
}
// Returns minimum xor value of pair in arr[0..n-1]
int minXOR(int arr[], int n)
{
    int min_xor = INT_MAX;  // Initialize result
    // create a True and insert first element in it
    TrieNode *root = getNode();
    insert(root, arr[0]);
    // Traversr all array elementd and find minimum xor
    // for every element
    for (int i = 1 ; i < n; i++)
    {
        // Find minimum XOR value of current element with
        // previous elements inserted in Trie
        min_xor = min(min_xor, minXORUtil(root, arr[i]));
        // insert current array value into Trie
        insert(root, arr[i]);
    }
    return min_xor;
}


No comments:

Post a Comment

Labels

GeeksforGeeks (1107) LeetCode (993) Algorithm (795) Review (766) to-do (633) LeetCode - Review (514) Classic Algorithm (324) Dynamic Programming (293) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Different Solutions (120) Bit Algorithms (118) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (107) HackerRank (89) Binary Tree (82) Binary Search (81) Graph Algorithm (74) Greedy Algorithm (72) DFS (67) LeetCode - Extended (62) Interview Corner (61) Stack (60) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (48) Binary Search Tree (46) USACO (46) Trie (45) Mathematical Algorithm (42) ACM-ICPC (41) Interval (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) LeetCode Hard (39) Recursive Algorithm (39) Matrix (38) String Algorithm (38) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Union-Find (34) Array (33) prismoskills (33) Segment Tree (32) Sliding Window (32) Data Structure Design (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Priority Queue (27) Random (27) Graph (26) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) Post-Order Traverse (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) Binary Indexed Trees (21) DFS + Review (21) Lintcode - Review (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) O(N) (20) Follow Up (19) Time Complexity (19) Two Pointers (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) Reverse Thinking (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Miscs (11) Princeton (11) Proof (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) Facebook Hacker Cup (10) HackerRank Easy (10) O(1) Space (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) DP-Multiple Relation (9) DP-Space Optimization (9) Divide and Conquer (9) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stack Overflow (9) Stock (9) System Design (9) TreeMap (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) LeetCode - DP (8) Left and Right Array (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Suffix Tree (8) Tech-Queries (8) Traversal Once (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) DP-Print Solution (6) Dijkstra (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) One Pass (6) Programming Pearls (6) Pruning (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) TreeSet (6) Xpost (6) reddit (6) AI (5) Algorithm - Brain Teaser (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) Cycle (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Pre-Sum (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (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) LeetCode - Recursive (4) LeetCode - TODO (4) MST (4) MinMax (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (3) Algorithm Design (3) B Tree (3) Big Data Algorithm (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) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) K (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) O(N) Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Stack - Smart (3) State Machine (3) Subtree (3) Transform Tree (3) Trie + DFS (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Ladder (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) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (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) Company-Snapchat (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) Edit Distance (2) Factor (2) Forward && Backward Scan (2) GoHired (2) Graham Scan (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) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Median (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Tree Without Tree Predefined (2) Word Break (2) Word Graph (2) Word Trie (2) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Augmented BST (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 Sarch Tree (1) Binary String (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) Cloest (1) Clone (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-Yelp (1) Compression Algorithm (1) Concurrency (1) Cont Improvement (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) Diagonal (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 - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (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) Machine Learning (1) Maintain State (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) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-End BFS (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Element (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) PreProcess (1) Probabilistic Data Structure (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) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) Square (1) Streaming Algorithm (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) Test Cases (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 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) Virtual Matrix (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (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