Code Implementation

import threading

class TrafficLight:
    def __init__(self):
        # 1 = North-South green, 0 = East-West green
        self.green = 1
        self.lock = threading.Lock()

    def carArrived(
        self,
        carId: int,           # ID of the car
        direction: int,       # 1: North, 2: East, 3: South, 4: West
        turnGreen: 'Callable[[], None]', # Turn light green for this direction
        crossCar: 'Callable[[], None]'   # Car crosses the intersection
    ) -> None:
        # North/South: direction 1 or 3, green == 1
        # East/West: direction 2 or 4, green == 0
        needGreen = 1 if direction in (1, 3) else 0
        with self.lock:
            if self.green != needGreen:
                turnGreen()
                self.green = needGreen
            crossCar()
      

#include <mutex>

class TrafficLight {
private:
    std::mutex mtx;
    int green; // 1: North-South, 0: East-West
public:
    TrafficLight() {
        green = 1;
    }

    void carArrived(
        int carId,                 // ID of the car
        int direction,             // 1: North, 2: East, 3: South, 4: West
        function<void()> turnGreen,// Turn light green for this direction
        function<void()> crossCar  // Car crosses the intersection
    ) {
        int needGreen = (direction == 1 || direction == 3) ? 1 : 0;
        std::lock_guard<std::mutex> lock(mtx);
        if (green != needGreen) {
            turnGreen();
            green = needGreen;
        }
        crossCar();
    }
};
      

import java.util.concurrent.locks.ReentrantLock;

class TrafficLight {
    private int green; // 1: North-South, 0: East-West
    private final ReentrantLock lock;

    public TrafficLight() {
        green = 1;
        lock = new ReentrantLock();
    }

    public void carArrived(
        int carId,                 // ID of the car
        int direction,             // 1: North, 2: East, 3: South, 4: West
        Runnable turnGreen,        // Turn light green for this direction
        Runnable crossCar          // Car crosses the intersection
    ) {
        int needGreen = (direction == 1 || direction == 3) ? 1 : 0;
        lock.lock();
        try {
            if (green != needGreen) {
                turnGreen.run();
                green = needGreen;
            }
            crossCar.run();
        } finally {
            lock.unlock();
        }
    }
}
      

class TrafficLight {
    constructor() {
        // 1 = North-South green, 0 = East-West green
        this.green = 1;
        this.lock = Promise.resolve();
    }

    carArrived(carId, direction, turnGreen, crossCar) {
        const needGreen = (direction === 1 || direction === 3) ? 1 : 0;
        this.lock = this.lock.then(() => {
            if (this.green !== needGreen) {
                turnGreen();
                this.green = needGreen;
            }
            crossCar();
        });
        return this.lock;
    }
}
      

Problem Description

The Traffic Light Controlled Intersection problem simulates a four-way intersection controlled by a traffic light. The intersection allows cars to approach from four directions: North (1), East (2), South (3), and West (4).

The intersection's traffic light can be green for either the North-South or East-West direction at any one time, but not both. Cars arrive at the intersection and must wait if the light is not green for their direction. When it is their turn, they can either change the light (if needed) and then cross.

You are to implement a class with a method carArrived that will be called for each car. The method receives:

• carId: The unique ID of the car
• direction: The direction the car comes from (1=North, 2=East, 3=South, 4=West)
• turnGreen: A function to turn the light green for this car's direction
• crossCar: A function to let the car cross the intersection

Key constraints:

• Only one direction can have a green light at a time.
• Cars must not cross unless the light is green for their direction.
• Switch the light only if necessary, i.e., don't switch if it's already green for that direction.
• Synchronization is required as cars may arrive concurrently (multi-threaded context).

Thought Process

The core challenge is to synchronize cars arriving from different directions so that only cars facing a green light can cross. Since the intersection is shared, we need to prevent race conditions where two cars might try to change the light at the same time, or cross when the light is not green for their direction.

The brute-force approach would be to let each car check the light and change it if needed, but without synchronization this can cause problems if two cars from different directions act at the same time. Therefore, we need some form of locking or mutual exclusion to ensure that checking and changing the light is atomic (cannot be interrupted).

The optimization is to use a lock (mutex) to ensure only one car can check and change the light at a time. This prevents inconsistent states and ensures correct order of operations. We also minimize unnecessary light switches by checking if the light is already green before switching.

Solution Approach

Let's break down the steps to implement the solution:

1. Represent the Traffic Light State:
   • Use a variable (e.g., green) to indicate which direction currently has the green light. For simplicity, use 1 for North-South and 0 for East-West.
2. Synchronization:
   • Use a lock (mutex) to ensure that only one car at a time can check and potentially change the light and cross.
3. Determine Required Light Direction:
   • For each car, determine if it needs North-South green (direction 1 or 3) or East-West green (direction 2 or 4).
4. Switch Light If Needed:
   • If the light is not already green for the car's direction, call turnGreen() and update the state variable.
5. Let the Car Cross:
   • After ensuring the light is green, call crossCar() to let the car cross the intersection.

This approach ensures that all operations are thread-safe, cars only cross when the light is green for their direction, and unnecessary light switches are avoided.

Example Walkthrough

Let's consider a scenario with four cars arriving in this order:

• Car 1: North (direction = 1)
• Car 2: East (direction = 2)
• Car 3: South (direction = 3)
• Car 4: West (direction = 4)

Step-by-step:

1. Car 1 (North): The light is initially green for North-South. Car 1 does not need to change the light and crosses immediately.
2. Car 2 (East): The light is green for North-South, but Car 2 needs East-West. Car 2 calls turnGreen() to switch the light, then crosses.
3. Car 3 (South): The light is now green for East-West, but Car 3 needs North-South. Car 3 calls turnGreen() to switch the light back, then crosses.
4. Car 4 (West): The light is green for North-South, but Car 4 needs East-West. Car 4 calls turnGreen() to switch the light, then crosses.

At each step, the lock ensures that only one car can make decisions about the light and cross at a time, preventing conflicts.

Time and Space Complexity

Brute-force approach:

• Without synchronization, checking and switching the light for each car is O(1), but this leads to race conditions and is incorrect.

• Each call to carArrived acquires the lock, checks the light, possibly switches it, and lets the car cross. All these are O(1) operations.
• Space complexity is O(1) since only a single state variable and lock are used regardless of the number of cars.
• Synchronization overhead is minimal and necessary for correctness.

Summary

The Traffic Light Controlled Intersection problem is about safe concurrent simulation of cars at a four-way intersection. The key insight is to use a lock to synchronize state changes, ensuring that only one car at a time can check and change the light and cross. This prevents race conditions and ensures that cars only cross when the light is green for their direction, and the light is only switched when necessary. The solution is elegant because it is both simple (O(1) per operation) and robust to concurrency, using minimal state and synchronization.