LeetCode 480 - Sliding Window Median


http://bookshadow.com/weblog/2017/01/08/leetcode-sliding-window-median/
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:
[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6
Therefore, return the median sliding window as [1,-1,-1,3,5,6].
Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.


X. TreeMap
TreeMap is used to implement an ordered MultiSet.
In this problem, I use two Ordered MultiSets as Heaps. One heap maintains the lowest 1/2 of the elements, and the other heap maintains the higher 1/2 of elements.

This implementation is faster than the usual implementation that uses 2 PriorityQueues, because unlike PriorityQueue, TreeMap can remove arbitrary element in logarithmic time.
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] res = new double[nums.length-k+1];
        TreeMap<Integer, Integer> minHeap = new TreeMap<Integer, Integer>();
        TreeMap<Integer, Integer> maxHeap = new TreeMap<Integer, Integer>(Collections.reverseOrder());
        
        int minHeapCap = k/2; //smaller heap when k is odd.
        int maxHeapCap = k - minHeapCap; 
        
        for(int i=0; i< k; i++){
            maxHeap.put(nums[i], maxHeap.getOrDefault(nums[i], 0) + 1);
        }
        int[] minHeapSize = new int[]{0};
        int[] maxHeapSize = new int[]{k};
        for(int i=0; i< minHeapCap; i++){
            move1Over(maxHeap, minHeap, maxHeapSize, minHeapSize);
        }
        
        res[0] = getMedian(maxHeap, minHeap, maxHeapSize, minHeapSize);
        int resIdx = 1;
        
        for(int i=0; i< nums.length-k; i++){
            int addee = nums[i+k];
            if(addee <= maxHeap.keySet().iterator().next()){
                add(addee, maxHeap, maxHeapSize);
            } else {
                add(addee, minHeap, minHeapSize);
            }
            
            int removee = nums[i];
            if(removee <= maxHeap.keySet().iterator().next()){
                remove(removee, maxHeap, maxHeapSize);
            } else {
                remove(removee, minHeap, minHeapSize);
            }

            //rebalance
            if(minHeapSize[0] > minHeapCap){
                move1Over(minHeap, maxHeap, minHeapSize, maxHeapSize);
            } else if(minHeapSize[0] < minHeapCap){
                move1Over(maxHeap, minHeap, maxHeapSize, minHeapSize);
            }
            
            res[resIdx] = getMedian(maxHeap, minHeap, maxHeapSize, minHeapSize);
            resIdx++;
        }
        return res;
    }

    public double getMedian(TreeMap<Integer, Integer> bigHeap, TreeMap<Integer, Integer> smallHeap, int[] bigHeapSize, int[] smallHeapSize){
        return bigHeapSize[0] > smallHeapSize[0] ? (double) bigHeap.keySet().iterator().next() : ((double) bigHeap.keySet().iterator().next() + (double) smallHeap.keySet().iterator().next()) / 2.0;
    }
    
    //move the top element of heap1 to heap2
    public void move1Over(TreeMap<Integer, Integer> heap1, TreeMap<Integer, Integer> heap2, int[] heap1Size, int[] heap2Size){
        int peek = heap1.keySet().iterator().next();
        add(peek, heap2, heap2Size);
        remove(peek, heap1, heap1Size);
    }
    
    public void add(int val, TreeMap<Integer, Integer> heap, int[] heapSize){
        heap.put(val, heap.getOrDefault(val,0) + 1);
        heapSize[0]++;
    }
    
    public void remove(int val, TreeMap<Integer, Integer> heap, int[] heapSize){
        if(heap.put(val, heap.get(val) - 1) == 1) heap.remove(val);
        heapSize[0]--;
    }
X. TreeSet
http://www.cnblogs.com/grandyang/p/6620334.html
这道题给了我们一个数组，还是滑动窗口的大小，让我们求滑动窗口的中位数。我想起来之前也有一道滑动窗口的题Sliding Window Maximum，于是想套用那道题的方法，可以用deque怎么也做不出，因为求中位数并不是像求最大值那样只操作deque的首尾元素。后来看到了史蒂芬大神的方法，原来是要用一个multiset集合，和一个指向最中间元素的iterator。我们首先将数组的前k个数组加入集合中，由于multiset自带排序功能，所以我们通过k/2能快速的找到指向最中间的数字的迭代器mid，如果k为奇数，那么mid指向的数字就是中位数；如果k为偶数，那么mid指向的数跟前面那个数求平均值就是中位数。当我们添加新的数字到集合中，multiset会根据新数字的大小加到正确的位置，然后我们看如果这个新加入的数字比之前的mid指向的数小，那么中位数肯定被拉低了，所以mid往前移动一个，再看如果要删掉的数小于等于mid指向的数(注意这里加等号是因为要删的数可能就是mid指向的数)，则mid向后移动一个。然后我们将滑动窗口最左边的数删掉，我们不能直接根据值来用erase来删数字，因为这样有可能删掉多个相同的数字，而是应该用lower_bound来找到第一个不小于目标值的数，通过iterator来删掉确定的一个数字
Inspired by this solution. to the problem: 295. Find Median from Data Stream
However instead of using two priority queue's we use two Tree Sets as we want O(logk) for remove(element). Priority Queue would have been O(k) for remove(element) giving us an overall time complexity of O(nk) instead of O(nlogk).
However there is an issue when it comes to duplicate values so to get around this we store the index into nums in our Tree Set. To break ties in our Tree Set comparator we compare the index.
public double[] medianSlidingWindow(int[] nums, int k) {
    Comparator<Integer> comparator = (a, b) -> nums[a] != nums[b] ? Integer.compare(nums[a], nums[b]) : a - b;
    TreeSet<Integer> left = new TreeSet<>(comparator.reversed());
    TreeSet<Integer> right = new TreeSet<>(comparator);
    
    Supplier<Double> median = (k % 2 == 0) ?
        () -> ((double) nums[left.first()] + nums[right.first()]) / 2 :
        () -> (double) nums[right.first()];
    
    // balance lefts size and rights size (if not equal then right will be larger by one)
    Runnable balance = () -> { while (left.size() > right.size()) right.add(left.pollFirst()); };
    
    double[] result = new double[nums.length - k + 1];
    
    for (int i = 0; i < k; i++) left.add(i);
    balance.run(); result[0] = median.get();
    
    for (int i = k, r = 1; i < nums.length; i++, r++) {
        // remove tail of window from either left or right
        if(!left.remove(i - k)) right.remove(i - k);

        // add next num, this will always increase left size
        right.add(i); left.add(right.pollFirst());
        
        // rebalance left and right, then get median from them
        balance.run(); result[r] = median.get();
    }
    
    return result;
}
二叉排序树（Binary Search Tree） / 堆（Heap）
维护二叉排序树hiSet与loSet，其中：

  hiSet的最小元素 > loSet的最大元素

  hiSet的大小 - loSet的大小 ∈ [0, 1]

获取中位数：

  若hiSet的大小 > loSet的大小，则返回hiSet.minValue
  
  否则，返回(hiSet.minValue + loSet.maxValue) / 2

新增元素：

  若hiSet为空，或者新元素 > hiSet.minValue，则加入hiSet
  
  否则加入loSet
  
  调整hiSet, loSet

移除元素：

  若hiSet包含目标元素，则从hiSet中移除
  
  否则，从loSet中移除
  
  调整hiSet, loSet

调整元素：

  若loSet的大小 > hiSet的大小，则将loSet的最大值弹出，加入hiSet
  
  否则，若hiSet的大小 - loSet的大小 > 1，则将hiSet的最小值弹出，加入loSet
private Comparator<Point> cmp = new Comparator<Point>(){ public int compare(Point a, Point b) { if (a.getX() != b.getX()) return Double.valueOf(b.getX()).compareTo(Double.valueOf(a.getX())); return Double.valueOf(b.getY()).compareTo(Double.valueOf(a.getY())); } }; private TreeSet<Point> hiSet = new TreeSet<>(cmp); private TreeSet<Point> loSet = new TreeSet<>(cmp); private double getMedian() { if (hiSet.size() > loSet.size()) { return hiSet.last().getX(); } return ((hiSet.last().getX()) + (loSet.first().getX())) / 2; } private void addValue(int val, int i) { Point p = new Point(val, i); if (hiSet.isEmpty() || hiSet.last().getX() < p.getX()) { hiSet.add(p); } else { loSet.add(p); } adjustSet(); } private void removeValue(int val, int i) { Point p = new Point(val, i); if (hiSet.contains(p)) { hiSet.remove(p); } else { loSet.remove(p); } adjustSet(); } private void adjustSet() { if (loSet.size() > hiSet.size()) { hiSet.add(loSet.pollFirst()); } else if (hiSet.size() > loSet.size() + 1) { loSet.add(hiSet.pollLast()); } } public double[] medianSlidingWindow(int[] nums, int k) { double[] ans = new double[nums.length - k + 1]; for (int i = 0; i < nums.length; i++) { if (i >= k) { removeValue(nums[i - k], i - k); } addValue(nums[i], i); if (i >= k - 1) { ans[i - k + 1] = getMedian(); } } return ans; }
https://discuss.leetcode.com/topic/74874/easy-to-understand-o-nlogk-java-solution-using-treemap
TreeMap is used to implement an ordered MultiSet.
In this problem, I use two Ordered MultiSets as Heaps. One heap maintains the lowest 1/2 of the elements, and the other heap maintains the higher 1/2 of elements.
This implementation is faster than the usual implementation that uses 2 PriorityQueues, because unlike PriorityQueue, TreeMap can remove arbitrary element in logarithmic time.

X.  PQ
https://leetcode.com/problems/sliding-window-median/discuss/96348/Java-solution-using-two-PriorityQueues
For those of you who made the same mistake: PriorityQueue maxHeap = new PriorityQueue<>((a,b)->(b-a)) won't pass test cases that involve comparing Integer MAX and MIN, change it to: PriorityQueue maxHeap = new PriorityQueue<>((a,b)->(b.compareTo(a)));

This is not O(n log(k)) time complexity, it's O(nk). One alternative is to use two balanced BSTs. A balanced BST can remove any element (not only the max or the min) in O(log(k)) time complexity. So the total time complexity will be O(n log(k)).
Almost the same idea of Find Median from Data Stream https://leetcode.com/problems/find-median-from-data-stream/
  1. Use two Heaps to store numbers. maxHeap for numbers smaller than current median, minHeap for numbers bigger than and equal to current median. A small trick I used is always make size of minHeap equal (when there are even numbers) or 1 element more (when there are odd numbers) than the size of maxHeap. Then it will become very easy to calculate current median.
  2. Keep adding number from the right side of the sliding window and remove number from left side of the sliding window. And keep adding current median to the result.
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
        new Comparator<Integer>() {
            public int compare(Integer i1, Integer i2) {
                return i2.compareTo(i1);
            }
        }
    );
 
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length - k + 1;
 if (n <= 0) return new double[0];
        double[] result = new double[n];
        
        for (int i = 0; i <= nums.length; i++) {
            if (i >= k) {
         result[i - k] = getMedian();
         remove(nums[i - k]);
            }
            if (i < nums.length) {
         add(nums[i]);
            }
        }
        
        return result;
    }
    
    private void add(int num) {
 if (num < getMedian()) {
     maxHeap.add(num);
 }
 else {
     minHeap.add(num);
 }
 if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
 }
        if (minHeap.size() - maxHeap.size() > 1) {
            maxHeap.add(minHeap.poll());
        }
    }
 
    private void remove(int num) {
 if (num < getMedian()) {
     maxHeap.remove(num);
 }
 else {
     minHeap.remove(num);
 }
 if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
 }
        if (minHeap.size() - maxHeap.size() > 1) {
            maxHeap.add(minHeap.poll());
        }
    }
 
    private double getMedian() {
 if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;
     
 if (maxHeap.size() == minHeap.size()) {
     return ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
 }
 else {
            return (double)minHeap.peek();
 }
    }
https://blog.csdn.net/MebiuW/article/details/54408831
  public double[] medianSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int m = n - k + 1; // 结果的尺寸
    double[] res = new double[m];
    // 两个堆，一个最大堆，一个最小
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
    for (int i = 0; i < n; i++) {
      int num = nums[i];
      // 让maxHeap始终保存小于一半的值，minHeap保存大于一半的，正好两半
      if (maxHeap.size() == 0 || maxHeap.peek() >= num)
        maxHeap.add(num);
      else
        minHeap.add(num);
      // 维护两个堆，保证两个堆得大小，要么保持一致（偶数时），要么maxHeap多一个（奇数时）
      if (minHeap.size() > maxHeap.size())
        maxHeap.add(minHeap.poll());
      if (maxHeap.size() > minHeap.size() + 1)
        minHeap.add(maxHeap.poll());
      // 如果需要输出
      if (i - k + 1 >= 0) {
        if (k % 2 == 1)
          res[i - k + 1] = maxHeap.peek();
        else
          res[i - k + 1] = (maxHeap.peek() / 2.0 + minHeap.peek() / 2.0); // 小心溢出
        // 移除并更新
        int toBeRemove = nums[i - k + 1];
        if (toBeRemove <= maxHeap.peek())
          maxHeap.remove(toBeRemove);
        else
          minHeap.remove(toBeRemove);
        // 维护两个堆，保证两个堆得大小，要么保持一致（偶数时），要么maxHeap多一个（奇数时）
        if (minHeap.size() > maxHeap.size())
          maxHeap.add(minHeap.poll());
        if (maxHeap.size() > minHeap.size() + 1)
          minHeap.add(maxHeap.poll());

      }
    }
    return res;

  }
https://discuss.leetcode.com/topic/74724/java-solution-using-two-priorityqueues
Almost the same idea of Find Median from Data Stream https://leetcode.com/problems/find-median-from-data-stream/
  1. Use two Heaps to store numbers. maxHeap for numbers smaller than current median, minHeap for numbers bigger than and equal to current median. A small trick I used is always make size of minHeap equal (when there are even numbers) or 1 element more (when there are odd numbers) than the size of maxHeap. Then it will become very easy to calculate current median.
  2. Keep adding number from the right side of the sliding window and remove number from left side of the sliding window. And keep adding current median to the result.
The documentation says remove(Object) takes linear time.
Then the overall runtime complexity is O(nk).
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
        new Comparator<Integer>() {
            public int compare(Integer i1, Integer i2) {
                return i2.compareTo(i1);
            }
        }
    );
 
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length - k + 1;
 if (n <= 0) return new double[0];
        double[] result = new double[n];
        
        for (int i = 0; i <= nums.length; i++) {
            if (i >= k) {
         result[i - k] = getMedian();
         remove(nums[i - k]);
            }
            if (i < nums.length) {
         add(nums[i]);
            }
        }
        
        return result;
    }
    
    private void add(int num) {
 if (num < getMedian()) {
     maxHeap.add(num);
 }
 else {
     minHeap.add(num);
 }
 if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
 }
        if (minHeap.size() - maxHeap.size() > 1) {
            maxHeap.add(minHeap.poll());
        }
    }
 
    private void remove(int num) {
 if (num < getMedian()) {
     maxHeap.remove(num);
 }
 else {
     minHeap.remove(num);
 }
 if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
 }
        if (minHeap.size() - maxHeap.size() > 1) {
            maxHeap.add(minHeap.poll());
        }
    }
 
    private double getMedian() {
 if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;
     
 if (maxHeap.size() == minHeap.size()) {
     return ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
 }
 else {
            return (double)minHeap.peek();
 }
    }


  public double[] medianSlidingWindow(int[] nums, int k) {
    if (k == 0) return new double[0];
    double[] ans = new double[nums.length - k + 1];
    int[] window = new int[k];
    for (int i = 0; i < k; ++i)
      window[i] = nums[i];
    Arrays.sort(window);
    for (int i = k; i <= nums.length; ++i) {
      ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;
      if (i == nums.length) break;
      remove(window, nums[i - k]);
      insert(window, nums[i]);
    }
    return ans;
  }
  
  // Insert val into window, window[k - 1] is empty before inseration
  private void insert(int[] window, int val) {
    int i = 0;
    while (i < window.length - 1 && val > window[i]) ++i;
    int j = window.length - 1;
    while (j > i) window[j] = window[--j];
    window[j] = val;
  }
  
  // Remove val from window and shrink it.
  private void remove(int[] window, int val) {
    int i = 0;
    while (i < window.length && val != window[i]) ++i;
    while (i < window.length - 1) window[i] = window[++i];
  }

X. Binary Search
https://zxi.mytechroad.com/blog/difficulty/hard/leetcode-480-sliding-window-median/
  public double[] medianSlidingWindow(int[] nums, int k) {
    if (k == 0) return new double[0];
    double[] ans = new double[nums.length - k + 1];
    int[] window = new int[k];
    for (int i = 0; i < k; ++i)
      window[i] = nums[i];
    Arrays.sort(window);
    for (int i = k; i <= nums.length; ++i) {
      ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;
      if (i == nums.length) break;
      remove(window, nums[i - k]);
      insert(window, nums[i]);
    }
    return ans;
  }
  
  // Insert val into window, window[k - 1] is empty before inseration
  private void insert(int[] window, int val) {
    int i = Arrays.binarySearch(window, val);
    if (i < 0) i = - i - 1;    
    int j = window.length - 1;
    while (j > i) window[j] = window[--j];
    window[j] = val;
  }
  
  // Remove val from window and shrink it.
  private void remove(int[] window, int val) {
    int i = Arrays.binarySearch(window, val);
    while (i < window.length - 1) window[i] = window[++i];
  }
  
https://www.jiuzhang.com/solution/sliding-window-median/

at
Labels: , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • HackerRank: Pacman A*
    HackerRank: Pacman A* In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes...
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • HackerRank: PacMan - BFS
    HackerRank: PacMan - BFS In the previous game, you performed DFS on the PacMan grid. It was seen that DFS might not always give the short...
  • DropBox Interview Misc
    https://paper.dropbox.com/doc/Interview-Notes-Dropbox-wl7npLjRBjrAKA5AOBsaM Behavioural https://www.paysa.com/blog/2017/04/05/what-to...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Print all sequences of given length | GeeksforGeeks
    Print all sequences of given length | GeeksforGeeks Given two integers k and n, write a function that prints all the sequences of length k...
  • LeetCode 988 - Smallest String Starting From Leaf
    https://leetcode.com/problems/smallest-string-starting-from-leaf/ Given the  root  of a binary tree, each node has a value from  0  to  2...
  • LeetCode 860 - Lemonade Change
    https://leetcode.com/problems/lemonade-change/description/ At a lemonade stand, each lemonade costs  $5 .  Customers are standing in a ...
  • Uber Interview
    优步面经 Email domain address typo, need to figure out and return correct domain name. e.g. yhaoo–> yahoo, giaml –> gmail, hmailot–> ...