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 (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) 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) Binary Tree (58) List (58) 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) Jobdu (39) Interval (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) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) 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 (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (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) Divide and Conquer (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) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (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) 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) Kadane’s Algorithm (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) 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) Parent-Only Tree (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