Design a deadlock-free traffic light controlled system at this intersection.

Implement the function void carArrived(carId, roadId, direction, turnGreen, crossCar) where:

  • carId is the id of the car that arrived.
  • roadId is the id of the road that the car travels on.
  • direction is the direction of the car.
  • turnGreen is a function you can call to turn the traffic light to green on the current road.
  • crossCar is a function you can call to let the current car cross the intersection.

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class TrafficLight {

    class Signal {
        // 1: road A
        int green = 1;
    }
    private final Signal signal;
    
    public TrafficLight() {
        signal = new Signal();
    }
    
    public void carArrived(
        int carId,           // ID of the car
        int roadId,          // ID of the road the car travels on. Can be 1 (road A) or 2 (road B)
        int direction,       // Direction of the car
        Runnable turnGreen,  // Use turnGreen.run() to turn light to green on current road
        Runnable crossCar    // Use crossCar.run() to make car cross the intersection 
    ) {
        
        synchronized(signal) {
            if (signal.green != roadId) {
                turnGreen.run();
                signal.green = roadId;
            }
            crossCar.run();
        }
    }
}

if turnGreen and crossCar were asynchronus. In that case we’d require to maintain callbacks.