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