Monday, August 8, 2016

Google – Remove Alarm


Google – Remove Alarm
有一堆Alarm, 每个alarm有三个值,start time, end time和priority。要求是把那些从没有成为过最高优先级的alarm给删除。
比如有这么几个alarms:
Alarm1 (1, 2, 1)
Alarm2 (1, 4, 2)
Alarm3 (3, 5, 3)
Alarm4 (3, 4, 2)
那么比如alarm1和alarm4就是要删除的。因为alarm1和alarm2同时开始,但是第二个优先级高,等第二个结束的时候第一个alarm早就结束了。所以第一个alarm从来没有到过最高优先级。alarm4也是一样。
[Solution]
这道题学会了一种新的算法:scan-line algorithm,中文叫扫描线算法。Leetcode里的the skyline problem使用的也是这种算法。
http://www.jiuzhang.com/qa/339/
思路就是把每个alarm的range拆成两条线,每条线记录一下信息:
1
2
3
4
5
6
7
8
9
10
11
12
13
class Line {
    int time;
    boolean isStart;
    int priority;
    int id;
    Line(int time, boolean isStart, int priority, int id) {
      this.time = time;
      this.isStart = isStart;
      this.priority = priority;
      this.id = id;
    }
  }
  1. 对所有Line按照time进行排序,如果time一样的,priority高的在前,如果priority也一样的,start在前,end在后。
  2. 遍历所有lines,边遍历边维护一个hash map和一个max heap.
    • hash map用来map priority to set of alarm id
    • max heap用来找最高的priority。
    1. 如果当前line是start, 那么把alarm id加入hash table对应priority的set里,并把priority加入max heap
    2. 如果当前line是end, 那么把alarm id从对应priority的set里删除,如果删除它之后对应的set为空了,那么把这个priority分别从hash table和max heap里删除。
    3. 每处理完一条line,都要从maxHeap里取出最大的priority,再到hash table里把该最大priority的alarm id全部mark一遍,表示这些alarm成为最高priority,不用删除。
  3. 最后删除那些没有被mark过的alarm
[Note]
因为这道题涉及到从maxHeap里删除元素,heap的结构是不支持search和delete功能的,所以本质上priority queue的remove方法就是对底层的internal array扫一遍来找到要删除的元素。时间是O(n),如果不对这个细节做特殊处理的话,整个算法的复杂度会变为O(n2)。
上面的连接里提到了一种Hash Heap的数据结构,就是用一个hash table来映射heap里每个元素的对应位置,这样在remove的时候就可以做到O(1)时间。


非常复杂的一道题,算法,思路和数据结构都很新颖。

class Alarm {
  int start;
  int end;
  int priority;
  Alarm(int start, int end, int priority) {
    this.start = start;
    this.end = end;
    this.priority = priority;
  }
}
class Solution {
  public void removeAlarm(List<Alarm> alarms) {
    if (alarms == null || alarms.isEmpty()) {
      return;
    }
    List<Line> Lines = new ArrayList<>();
    for (int i = 0; i < alarms.size(); i++) {
      Alarm alarm = alarms.get(i);
      Lines.add(new Line(alarm.start, true, alarm.priority, i));
      Lines.add(new Line(alarm.end, false, alarm.priority, i));
    }
    Collections.sort(Lines, new Comparator<Line>() {
      public int compare(Line a, Line b) {
        if (a.time == b.time && a.priority == b.priority) {
          return a.isStart? -1 : 1;
        }
        else if (a.time == b.time) {
          return -(a.priority - b.priority);
        }
        return a.time - b.time;
      }
    });
    Map<Integer, Set<Integer>> priorityMap = new HashMap<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(5, Collections.reverseOrder());
    Set<Integer> mark = new HashSet<>();
    for (Line Line : Lines) {
      if (Line.isStart) {
        if (!priorityMap.containsKey(Line.priority)) {
          priorityMap.put(Line.priority, new HashSet<>());
          maxHeap.offer(Line.priority);
        }
        priorityMap.get(Line.priority).add(Line.id);
      }
      else {
        priorityMap.get(Line.priority).remove(Line.id);
        if (priorityMap.get(Line.priority).isEmpty()) {
          priorityMap.remove(Line.priority);
          maxHeap.remove(Line.priority);
        }
      }
      if (!maxHeap.isEmpty()) {
        int top = maxHeap.peek();
        for (int id : priorityMap.get(top)) {
          mark.add(id);
        }
      }
    }
    for (int i = 0; i < alarms.size(); i++) {
      if (!mark.contains(i)) {
        System.out.println(i);
      }
    }
  }
  private class Line {
    int time;
    boolean isStart;
    int priority;
    int id;
    Line(int time, boolean isStart, int priority, int id) {
      this.time = time;
      this.isStart = isStart;
      this.priority = priority;
      this.id = id;
    }
  }
}
http://www.jiuzhang.com/qa/339/

有一个需要clarify的地方是,如果和其他的alert一起同时成为最高的优先度,这种需要去掉么?
下面的解答基于不需要去掉与其他alarm同时成为最高优先度的那些alarms:
  1. 将起始时间终止,终止时间和对应的优先度以及alarm的id打散。一个alarm会变成两个item:(start_time, alarm_id, priority, is_start=true), (end_time, alarm_id, priority, is_start=false)
  2. 把所有的2N个items排序。按照第一个field time从小到大排序。
  3. 依次访问排序后的每个item
    1. 如果is_start=true,那么 check priority 是否在某个集合中,如果不在的话就create一个entry 给这个priority,将alarm_id添加到该priority的一个list里,表示当前是该priority的alarms有哪些。entry包括两个部分,一个是priority,作为key,第二个是一个list,表示有哪些alarms,作为value。
    2. 如果is_start=false,那么 找到集合中priority对应的entry,然后把alarm_id从里面删除,如果entry里的list空了,就在集合中删除这条entry。
    3. 上面的操作完成后,检查目前集合中priority最高的entry,把这个entry里的alarms都标记为成为过最高优先级的。
  4. 最后再check所有的alarm,看看哪些没有被标记过。
这中间有一个优化需要做的是,需要把list分为已经标记过成为最高优先级的,和没有标记过成为最高优先级的。否则反复标记同一个alarm成为过最高优先级会耗费时间复杂度。 这个list,本身因为需要支持插入和删除的话,那么其实实际上应该是两个hashset。
整体的时间复杂度是(NlogN + NlogP),N为alarms的个数,P为Priority的个数,NlogN是排序的复杂度,NlogP是后面统计处理的时候的复杂度。至于这个集合既需要做key-value的查询,又需要找最大值,那么自然是HashHeap。这种数据机构,我们会在《九章算法强化班》中讲解。
这种算法的名字叫做:扫描线算法。是Google的大爱。
类似的题目是这题,也是Google出过的题:
http://www.lintcode.com/en/problem/building-outline/
Read full article from Google – Remove Alarm

No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (632) to-do (596) Classic Algorithm (334) Review (330) Classic Interview (299) Dynamic Programming (263) Google Interview (229) LeetCode - Review (224) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Interview Corner (61) Greedy Algorithm (60) List (58) Binary Tree (56) DFS (54) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (44) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Interval (38) Jobdu (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Trie (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) System Design (8) Tech-Queries (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Suffix Tree (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) Time Complexity (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Kadane’s Algorithm (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) 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) Sweep Line (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) 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) Master Theorem (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts