Thursday, June 2, 2016

LeetCode 352 - Data Stream as Disjoint Intervals


http://www.cnblogs.com/grandyang/p/5548284.html
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]
Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
这道题说有个数据流每次提供一个数字,然后让我们组成一系列分离的区间,这道题跟之前那道Insert Interval很像,思路也很像,每进来一个新的数字val,我们都生成一个新的区间[val, val],然后将其插入到当前的区间里,注意分情况讨论,无重叠,相邻,和有重叠分开讨论处理


Use TreeMap to easily find the lower and higher keys, the key is the start of the interval. Merge the lower and higher intervals when necessary. The time complexity for adding is O(logN) since lowerKey(), higherKey(), put() and remove() are all O(logN). It would be O(N) if you use an ArrayList and remove an interval from it.
TreeMap<Integer, Interval> tree; public SummaryRanges() { tree = new TreeMap<>(); } public void addNum(int val) { if(tree.containsKey(val)) return; Integer l = tree.lowerKey(val); Integer h = tree.higherKey(val); if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) { tree.get(l).end = tree.get(h).end; tree.remove(h); } else if(l != null && tree.get(l).end + 1 >= val) { tree.get(l).end = Math.max(tree.get(l).end, val); } else if(h != null && h == val + 1) { tree.put(val, new Interval(val, tree.get(h).end)); tree.remove(h); } else { tree.put(val, new Interval(val, val)); } } public List<Interval> getIntervals() { return new ArrayList<>(tree.values()); }
http://www.guoting.org/leetcode/leetcode-352-data-stream-as-disjoint-intervals/
http://www.allenlipeng47.com/blog/index.php/2016/06/13/data-stream-as-disjoint-intervals/
https://discuss.leetcode.com/topic/46887/java-solution-using-treemap-real-o-logn-per-adding
这题用Maptree会通过map.lowerKey, map.higherKey很快定位到当前数所处在哪两个interval之间,从而进行高效的比较与合并。
Use TreeMap and put start as key, (start, end) as value in TreeMap. Basically, ; there will be 3 conditions when adding a new value: add 4 to (5, 6), (8, 9); add 6 to (5, 5); add 4 to (5, 5):
add_middle              add_left              add_right
Besides, there are 2 exceptions: add 6 to (5, 7); add 6 to (6, 6):
exception1       exception2
public class SummaryRanges {
    TreeMap<Integer, Interval> tree;

    public SummaryRanges() {
        tree = new TreeMap<>();
    }

    public void addNum(int val) {
        if(tree.containsKey(val)) return;
        Integer l = tree.lowerKey(val);
        Integer h = tree.higherKey(val);
        if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
            tree.get(l).end = tree.get(h).end;
            tree.remove(h);
        } else if(l != null && tree.get(l).end + 1 >= val) {
            tree.get(l).end = Math.max(tree.get(l).end, val);
        } else if(h != null && h == val + 1) {
            tree.put(val, new Interval(val, tree.get(h).end));
            tree.remove(h);
        } else {
            tree.put(val, new Interval(val, val));
        }
    }

    public List<Interval> getIntervals() {
        return new ArrayList<>(tree.values());
    }
}
http://dartmooryao.blogspot.com/2016/06/leetcode-352-data-stream-as-disjoint.html
(1) Use TreeMap to store the intervals. The key is the start of interval, value is the Interval object.
(2) For each addNum, we first create a Interval object using the val as start and end.
(3) Get the floorKey from the TreeMap, if the prev Interval is connected to this input value, update the current interval by smaller start, and larger end. Also update the key.
(4) Get the ceilingKey from the TreeMap, if there is overlap, remove the interval from the map. Then update the current interval's end.
(5) Put the current interval into the map.

    TreeMap<Integer, Interval> map;

    /** Initialize your data structure here. */
    public SummaryRanges() {
        map = new TreeMap<Integer, Interval>();
    }
  
    public void addNum(int val) {
        Integer prevKey = map.floorKey(val);
        int thisKey = val;
        Interval thisInt = new Interval(val, val);
        if(prevKey!=null && map.get(prevKey).end+1 >= val){
            thisKey = map.get(prevKey).start;
            thisInt.start = Math.min(map.get(prevKey).start, val);
            thisInt.end = Math.max(map.get(prevKey).end, val);
        }
      
        Integer nextKey = map.ceilingKey(val);
        if(nextKey!=null && nextKey-1==val){
            thisInt.end = map.get(nextKey).end;
            map.remove(nextKey);
        }
      
        map.put(thisKey, thisInt);
    }
  
    public List<Interval> getIntervals() {
        return new ArrayList(map.values());
    }
X.
http://bookshadow.com/weblog/2016/05/31/leetcode-data-stream-as-disjoint-intervals/
如果合并次数非常多,与数据流的规模相比不相交区间的数目很少,应当做怎样的优化?

解题思路:
利用TreeSet数据结构,将不相交区间Interval存储在TreeSet中。

TreeSet底层使用红黑树实现,可以用log(n)的代价实现元素查找。

每次执行addNum操作时,利用TreeSet找出插入元素val的左近邻元素floor(start值不大于val的最大Interval),以及右近邻元素higher(start值严格大于val的最小Interval)

然后根据floor, val, higher之间的关系决定是否对三者进行合并。
如果合并次数非常多,与数据流的规模相比不相交区间的数目很少,应当做怎样的优化?

解题思路:
利用TreeSet数据结构,将不相交区间Interval存储在TreeSet中。

TreeSet底层使用红黑树实现,可以用log(n)的代价实现元素查找。

每次执行addNum操作时,利用TreeSet找出插入元素val的左近邻元素floor(start值不大于val的最大Interval),以及右近邻元素higher(start值严格大于val的最小Interval)

然后根据floor, val, higher之间的关系决定是否对三者进行合并。
public class SummaryRanges {

    /** Initialize your data structure here. */
    
    private TreeSet<Interval> intervalSet; 
    
    public SummaryRanges() {
        intervalSet = new TreeSet<Interval>(new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
    }
    
    public void addNum(int val) {
        Interval valInterval = new Interval(val, val);
        Interval floor = intervalSet.floor(valInterval);
        if (floor != null) {
            if (floor.end >= val) {
                return;
            } else if (floor.end + 1 == val) {
                valInterval.start = floor.start;
                intervalSet.remove(floor);
            }
        }
        Interval higher = intervalSet.higher(valInterval);
        if (higher != null && higher.start == val + 1) {
            valInterval.end = higher.end;
            intervalSet.remove(higher);
        }
        intervalSet.add(valInterval);
    }
    
    public List<Interval> getIntervals() {
        return Arrays.asList(intervalSet.toArray(new Interval[0]));
    }
}
X. http://www.mobile-open.com/2016/961231.html
建立一棵二叉搜索树,树的节点值用interval表示,其实就是类似于“区间树”节点值是个区间,这些区间不相交。建立树之后中序遍历输出结果。
插入的过程较为麻烦,插入需要考虑一个节点的两端点,情况较多,具体见代码注释。
X.
http://blog.csdn.net/qq508618087/article/details/51553166
思路: 用一个数组来保存结果, 然后每次搜索的时候用lower_bound可以找到第一个大于等于要插入的值的区间, 当前要插入的值可能会正好等于上个区间的end+1, 因此需要做个判断. 把能合并的区间都从数组中删除, 最后插入一个新的区间.
关于follow-up, 如果合并的操作非常多但是最后区间可能很少, 这种情况下不适合直接用vector, 因为他的合并操作需要移位, 故时间复杂度是O(n), 频繁的移位会造成时间复杂度大大增加. 一个更好的解决办法是使用set, 因为二叉搜索树插入查找都可以在O(log n)完成, 只需要在返回结果的时候将set中的值放到vector中即可.

http://dartmooryao.blogspot.com/2016/06/leetcode-352-data-stream-as-disjoint.html
This time I do it using a binary search.
(1) The Idea is to find the first interval in the list that's larger than the input value, then check the higer interval and lower interval to merge them.
(2) Here is a trick to make the code clean: We create an interval from the input first. Then if we find an overlap, we delete the interval from the list!! Do it separately for the higher interval and lower interval!
(3) The time complexity here is actually O(N) for addNum and O(1) for getIntervals. Why? For the addNum, although we use a binary search, the time complexity to delete a interval from arrayList is O(N).
    List<Interval> list = new ArrayList<>();

    /** Initialize your data structure here. */
    public SummaryRanges() {
       
    }
   
    public void addNum(int val) {
        int idx = findFirstLarger(val);
        Interval newInt = new Interval(val, val);
        if(idx>0 && list.get(idx-1).end+1 >= val){
            Interval before = list.remove(idx-1);
            newInt.start = Math.min(before.start, newInt.start);
            newInt.end = Math.max(before.end, newInt.end);
            idx--;
        }

        if(idx<list.size() && list.get(idx).start-1 <= val){
            Interval after = list.remove(idx);
            newInt.start = Math.min(after.start, newInt.start);
            newInt.end = Math.max(after.end, newInt.end);
        }
       
        list.add(idx, newInt);
    }
   
    public List<Interval> getIntervals() {
        return list;
    }
   
    private int findFirstLarger(int val){
        int start = 0, end = list.size();
        while(start<end){
            int mid = start+(end-start)/2;
            if(list.get(mid).start<val){
                start = mid+1;
            }else{
                end = mid;
            }
        }
        return start;
    }

https://leetcode.com/discuss/105742/simple-java-solution-using-insert-interval
Basic idea is to use the method of 57. Insert interval. What we have to change here is to add some code to merge intervals with distance 1.

public class SummaryRanges {

    /** Initialize your data structure here. */
    List<Interval> summary;
    public SummaryRanges() {
        summary = new ArrayList<>();
    }

    public void addNum(int val) {
        Interval cur = new Interval(val,val);
        List<Interval> rst = new ArrayList<Interval>();
        int pos = 0;
        for(Interval interval : summary){
            //non Overlap
            if(cur.end + 1 < interval.start) {
                rst.add(interval);
                continue;
            }
            if(cur.start > interval.end + 1){
                rst.add(interval);
                pos++;
                continue;
            }
            //Overlap // where is the remove?
            if(cur.start - 1 == interval.end) cur.start = interval.start;
            else if(cur.end + 1 == interval.start) cur.end = interval.end;
            //Merge
            else{
                cur.start = Math.min(cur.start, interval.start);
                cur.end = Math.max(cur.end, interval.end);
            }
        }
        rst.add(pos, cur);
        summary = new ArrayList<Interval>(rst);
    }

    public List<Interval> getIntervals() {
        return summary;
    }
}
Returns the greatest key strictly less than the given key, or null if there is no such key.

    public K lowerKey(K key
Returns the least key strictly greater than the given key, or null if there is no such key.
    public K higherKey(K key)

https://discuss.leetcode.com/topic/47084/java-fast-log-n-solution-186ms-without-using-the-treemap-but-a-customized-bst
Java fast log (N) solution (186ms) without using the TreeMap but a customized BST
    class BSTNode {
        Interval interval;
        BSTNode left;
        BSTNode right;
        BSTNode(Interval in){
            interval = in;
        }
    }
    
    BSTNode findMin(BSTNode root) {
        if (root == null) return null;
        if (root.left == null ) return root;
        else return findMin(root.left);
    }
    
    BSTNode remove(Interval x, BSTNode root) {
        if (root == null) return null;
        else if ( x == null ) return root;
        else if (x.start > root.interval.end ) {
            root.right = remove(x, root.right);
        } else if (x.end < root.interval.start ) {
            root.left = remove(x, root.left);
        } else if ( root.left != null && root.right != null) {
            root.interval = findMin(root.right).interval;
            root.right = remove( root.interval, root.right);
        } else {
            root = ( root.left != null ) ? root.left : root.right;
        }
        return root;
    }
    
    BSTNode findKey(int val, BSTNode root) {
        if (root == null) return null;
        if (root.interval.start > val) {
            return findKey(val, root.left);
        } else if (root.interval.end < val) {
            return findKey(val, root.right);
        } else return root;
    }
    
    BSTNode addKey(int val, BSTNode root) {
        if (root == null) {
            root = new BSTNode( new Interval(val, val) ); 
        } else if (root.interval.start > val) {
            root.left = addKey(val, root.left);
        } else if (root.interval.end < val) {
            root.right = addKey(val, root.right);
        }  
        return root;
    }
    void inOrder(BSTNode root) {
        if (root != null) {
            inOrder(root.left);
            list.add(root.interval);
            inOrder(root.right);
        }
    }
    
    /** Initialize your data structure here. */
    BSTNode root;
    List<Interval> list = new ArrayList();
    public SummaryRanges() {
        root = null;
    }
    
    public void addNum(int val) {
        if (root == null) {
            root = addKey(val, root);
        } else {
            if ( findKey(val, root) != null) return;
            BSTNode left = findKey(val-1, root);
            BSTNode right = findKey(val+1, root);
            if (left == null && right == null) {
                root = addKey(val, root);
            } else if (left != null && right == null) {
                left.interval.end++;
            } else if (left == null && right != null) {
                right.interval.start--;
            } else {
                Interval l = left.interval;
                int e = right.interval.end;
                root = remove(right.interval, root);
                l.end = e;
            }
        }
    }
    
    public List<Interval> getIntervals() {
        list.clear();
        inOrder(root);
        return list;
    }
}

No comments:

Post a Comment

Labels

GeeksforGeeks (1107) LeetCode (985) Algorithm (795) Review (759) to-do (631) LeetCode - Review (506) Classic Algorithm (324) Dynamic Programming (292) 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 Search (81) Binary Tree (80) Graph Algorithm (74) Greedy Algorithm (72) DFS (66) LeetCode - Extended (62) Interview Corner (61) Stack (60) List (58) Advanced Data Structure (56) Codility (54) BFS (53) 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) Recursive Algorithm (39) LeetCode Hard (38) 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) TopCoder (23) Algorithm Game (22) Hash (22) Post-Order Traverse (22) Binary Indexed Trees (21) Bisection Method (21) DFS + Review (21) Lintcode - Review (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) Follow Up (19) O(N) (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) 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) Find Rule (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) 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) Tree Without Tree Predefined (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