Google – Stop All Way


Google – Stop All Way
一道非常有意思的Design题。Google engineer们的脑洞也是一个比一个大。
题目很简单,就是design data structure来实现美国的stop all way路口,具体就是实现
void arriveCar(Lane lane, Car car);
Car getNextCar();
[Solution]
首先对于Car和Lane的design. 每个Lane都会有一个Queue of Car, 每个Car也会有一个Lane object.
然后对于schedule, 有两种solution。
注意考虑下多线程的情况。
[Solution #1]
第一种是round robin。1,2,3,4,四个路口,比如这次从路口1走了一辆车,下次从路口2开始扫描,看有没有车等着,有就从2走,再下次就从3开始扫。如果路口2没有车,那就看3,扫完一圈回到路口1,要是路口1有车,就走,没有,就说明此时此刻4个路口都没有车。
但是这样的解法看上去就不太合理。因为如果想象一下现实生活中的场景,其实会是一个multithreading的过程,4个路口相当于4个threads不停的有车来,而同一时间只能走一辆车,先来先走。
那么对于round robin的方法,会有bug。比如现在4个路口都没有车,然后getNextCar()和arriveCar(4, car)被两个threads同时call,那按照上面说的从0开始扫,发现没车,到1,结果这时候又有一个thread call arriveCar(3, car), 那么这样的情况扫到路口3的时候发现有车,就会让路口3的车先走。但事实却是路口4的车先到。
[Solution #2]
Maintain一个queue来记录schedule的顺序,在getNextCar()的时候只要poll出queue里的第一辆车就可以了.
当arriveCar(Lane lane, Car car)的时候,如果当前lane里一辆车都没有,把新来的这辆车offer进schedule queue. 否则只需要offer进当前路口自己的queue就可以了。
当getNextCar()之后,将next car所属车道的下一辆车offer进schedule queue。
这样即可以保证先到先走的顺序,用一个BlockingQueue也可以解决multithreading的情况。
class Car {
  int id;
  Lane lane;
   
  public Car(int id, Lane lane) {
    this.id = id;
    this.lane = lane;
  }
   
}
   
class Lane {
  Queue<Car> queue;
  int id;
   
  public Lane(int id) {
    this.id = id;
    this.queue = new LinkedList<>();
  }
}
 
// round robin - not survive multithreading
class Solution {
   
  List<Lane> lanes = new ArrayList<>();
  lanes.add(new Lane(0));
  lanes.add(new Lane(1));
  lanes.add(new Lane(2));
  lanes.add(new Lane(3));
 
  int currLane = 0;
     
  public void arriveCar(Car car, Lane lane) {
    if (car == null || lane == null) {
      return;
    }
    lane.queue.offer(car);
  }
   
  // round robin - not survive multithreading
  // 比如现在所有车道都没有车,currlane在0。
  // 然后getNextCar()和arriveCar(car, 4)同时被两个threads call
  // currlane从0开始循环,循环到1车道的时候又有另个一thread call了arriveCar(car, 3)
  // 结果会变成3车道的车比4车道的车先走,但事实是4车道的车先到。
  public Car getNextCar() {
    Car result = null;
    int tmp = currLane;
    while (lanes.get(tmp).queue.isEmpty()) {
      tmp = (tmp + 1) % 4;
      if (tmp == currLane) {
        break;
      }
    }
    if (!lanes.get(tmp).queue.isEmpty()) {
      result = lanes.get(tmp).poll();
      currLane = (tmp + 1) % 4;
    }
     
    return result;
  }
}
 
 
class Solution2 {
  Lane lane0 = new Lane(0);
  Lane lane1 = new Lane(1);
  Lane lane0 = new Lane(2);
  Lane lane1 = new Lane(3);
   
  Queue<Car> next = new LinkedList<>();
   
   
  public void arriveCar(Car car, Lane lane) {
    if (car == null || lane == null) {
      return;
    }
     
    if (lane.queue.isEmpty()) {
      next.offer(car);
    }
    car.lane = lane;
    lane.queue.offer(car);
  }
   
  public Car getNext() {
    if (next.isEmpty()) {
      return null;
    }
     
    Car result = next.poll();
    result.lane.queue.poll();
    if (!result.lane.queue.isEmpty()) {
      next.offer(result.lane.queue.peek());
    }
     
    return result;
  }
}
Read full article from Google – Stop All Way

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