Problem Description

This problem asks you to design a traffic light controller for an intersection where two roads meet. Road A runs North-South (directions 1 and 2), and Road B runs East-West (directions 3 and 4).

The intersection has the following rules:

• Each road has a traffic light that can be either green or red
• When a light is green, cars from both directions on that road can cross
• When a light is red, cars must wait
• Only one road can have a green light at a time - when Road A is green, Road B must be red, and vice versa
• Initially, Road A has a green light and Road B has a red light

You need to implement the carArrived method that gets called whenever a car arrives at the intersection. This method receives:

• carId: The unique identifier of the arriving car
• roadId: Which road the car is on (1 for Road A, 2 for Road B)
• direction: The direction the car is traveling (1-4)
• turnGreen: A function to change the traffic light to green on the current road
• crossCar: A function to let the current car cross the intersection

The key requirements are:

1. Avoid deadlock - cars should not get stuck waiting forever
2. Prevent collisions - cars from different roads should never cross at the same time
3. Correct light management - only call turnGreen() when actually changing the light from red to green (calling it when already green is wrong)

The solution uses a lock to ensure thread safety and tracks which road currently has the green light. When a car arrives, it acquires the lock, checks if its road needs the light changed, crosses the intersection, then releases the lock. This ensures cars cross one at a time and the light changes only when necessary.

Intuition

The core challenge here is coordinating multiple cars arriving from different roads while ensuring they don't collide and don't deadlock. Let's think through what could go wrong:

1. Race conditions: If multiple cars try to cross simultaneously without coordination, cars from different roads might collide
2. Deadlock: If we're not careful with our synchronization, cars could end up waiting for each other indefinitely
3. Incorrect light changes: We need to track which road currently has the green light to avoid unnecessary turnGreen() calls

The key insight is that the intersection itself is a shared resource that only one car can use at a time. This immediately suggests using a mutual exclusion mechanism - a lock.

Why does a simple lock work here? Consider what happens:

• When a car arrives, it must wait for exclusive access to the intersection
• Once it has access, it can safely check if the light needs changing
• No other car can interfere during this critical section
• After crossing, it releases the lock for the next car

The beauty of this approach is that it naturally handles the traffic light state. We only need to track which road currently has green (self.road). When a car from a different road arrives:

• It compares its roadId with the current green road
• If different, it calls turnGreen() and updates the tracked state
• If same, the light is already green, so just cross

This serialization through the lock ensures:

• No collisions: Only one car crosses at a time
• No deadlock: The lock is always released after crossing, so the next car can proceed
• Correct light management: We only change lights when switching roads

The solution is elegant because it transforms a complex traffic coordination problem into a simple critical section problem - whoever holds the lock gets to make decisions about the intersection state and cross safely.

Solution Approach

The implementation uses a mutex lock pattern to ensure thread-safe access to the intersection. Let's walk through the solution step by step:

Data Structures Used

1. Lock (Mutex): self.lock = Lock() - A threading lock that ensures mutual exclusion
2. State Variable: self.road = 1 - Tracks which road currently has the green light (initialized to Road A)

Implementation Details

The __init__ method sets up our traffic light controller:

def __init__(self):
    self.lock = Lock()  # Create a mutex for synchronization
    self.road = 1       # Road A (1) initially has green light

The carArrived method implements the core logic:

def carArrived(self, carId, roadId, direction, turnGreen, crossCar):
    self.lock.acquire()        # Step 1: Acquire exclusive access
    if self.road != roadId:    # Step 2: Check if light change needed
        self.road = roadId     # Step 3: Update state
        turnGreen()             # Step 4: Change the light
    crossCar()                  # Step 5: Let car cross
    self.lock.release()         # Step 6: Release lock for next car

Algorithm Flow

1. Acquire Lock: When a car arrives, it first acquires the lock. If another car is currently crossing, this car will block and wait.

2. Check Light State: Once the lock is acquired, check if the car's road (roadId) matches the road that currently has green (self.road).

3. Change Light if Needed:

   • If self.road != roadId, the car is on a different road than the one with green light
   • Update self.road to the new road
   • Call turnGreen() to change the traffic light

4. Cross Intersection: Call crossCar() to let the current car cross safely

5. Release Lock: Release the lock so the next waiting car can proceed

Why This Works

• Prevents Collisions: The lock ensures only one car can be in the critical section (checking lights and crossing) at a time
• Avoids Deadlock: The lock is always released after crossing, guaranteeing progress
• Correct Light Management: We only call turnGreen() when actually switching roads, never when the light is already green for the current road
• Thread Safety: All state changes happen within the locked section, preventing race conditions

The pattern used here is essentially a monitor pattern where the lock protects the shared state (self.road) and ensures atomic execution of the traffic control logic.

Example Walkthrough

Let's walk through a scenario with 4 cars arriving at the intersection to see how the solution handles traffic coordination:

Initial State: Road A has green light (self.road = 1), Road B has red light

Car Sequence:

1. Car #1 arrives on Road A (roadId=1)
2. Car #2 arrives on Road B (roadId=2)
3. Car #3 arrives on Road B (roadId=2)
4. Car #4 arrives on Road A (roadId=1)

Step-by-Step Execution:

Car #1 (Road A):

• Acquires lock (no competition)
• Checks: self.road (1) == roadId (1) → Already green, no light change needed
• Calls crossCar() to cross intersection
• Releases lock
• State remains: self.road = 1

Car #2 (Road B):

• Acquires lock (might wait if Car #1 still crossing)
• Checks: self.road (1) != roadId (2) → Different road, needs light change
• Updates: self.road = 2
• Calls turnGreen() to change light to Road B
• Calls crossCar() to cross intersection
• Releases lock
• New state: self.road = 2

Car #3 (Road B):

• Acquires lock (waits for Car #2 to finish)
• Checks: self.road (2) == roadId (2) → Already green, no light change needed
• Calls crossCar() to cross intersection
• Releases lock
• State remains: self.road = 2

Car #4 (Road A):

• Acquires lock (waits for Car #3 to finish)
• Checks: self.road (2) != roadId (1) → Different road, needs light change
• Updates: self.road = 1
• Calls turnGreen() to change light back to Road A
• Calls crossCar() to cross intersection
• Releases lock
• New state: self.road = 1

Key Observations:

• The light only changes twice: when Car #2 switches from Road A to B, and when Car #4 switches back from Road B to A
• Cars #1 and #3 don't trigger light changes since they're on roads that already have green
• The lock ensures cars cross one at a time, preventing collisions
• Each car releases the lock after crossing, preventing deadlock

This example demonstrates how the solution efficiently manages traffic flow with minimal light changes while maintaining safety.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

• The carArrived method performs a fixed number of operations regardless of input size
• lock.acquire() - O(1) in the best case (no contention), but can be O(n) in worst case where n is the number of waiting threads
• Comparison self.road != roadId - O(1)
• Assignment self.road = roadId - O(1)
• Function calls turnGreen() and crossCar() - O(1) (assuming these are simple callback operations)
• lock.release() - O(1)
• Overall amortized time complexity per operation is O(1)

Space Complexity: O(1)

• The class maintains only two instance variables:
  • self.lock - a Lock object which takes constant space
  • self.road - an integer variable storing the current road ID
• No additional data structures are created that grow with input
• The method parameters use constant space regardless of the number of cars
• No recursive calls that would increase the call stack
• Total space usage remains constant: O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Release the Lock on Exception

The current implementation has a critical flaw: if turnGreen() or crossCar() throws an exception, the lock will never be released, causing a permanent deadlock where no other car can ever cross the intersection.

Problem Code:

def carArrived(self, carId, roadId, direction, turnGreen, crossCar):
    self.lock.acquire()
    if self.road != roadId:
        self.road = roadId
        turnGreen()  # If this throws an exception...
    crossCar()       # Or if this throws an exception...
    self.lock.release()  # This line never executes!

Solution: Use a context manager or try-finally block:

def carArrived(self, carId, roadId, direction, turnGreen, crossCar):
    with self.lock:  # Automatically releases lock even on exception
        if self.road != roadId:
            self.road = roadId
            turnGreen()
        crossCar()

Or with try-finally:

def carArrived(self, carId, roadId, direction, turnGreen, crossCar):
    self.lock.acquire()
    try:
        if self.road != roadId:
            self.road = roadId
            turnGreen()
        crossCar()
    finally:
        self.lock.release()  # Always executes

2. Using Road ID Instead of Proper Road Grouping

A subtle pitfall is confusing the road ID with direction grouping. The problem states:

• Road A: directions 1 and 2 (North-South)
• Road B: directions 3 and 4 (East-West)

Some might incorrectly map roadId directly to direction or assume roadId equals 1 or 2 based on direction numbers.

Incorrect Implementation:

def carArrived(self, carId, roadId, direction, turnGreen, crossCar):
    with self.lock:
        # Wrong: using direction to determine road
        current_road = 1 if direction <= 2 else 2
        if self.road != current_road:
            self.road = current_road
            turnGreen()
        crossCar()

Correct: Trust the roadId parameter provided - it already indicates which road (1 for Road A, 2 for Road B).

3. Calling turnGreen() Unnecessarily

A common mistake is calling turnGreen() every time a car arrives, even when the light is already green for that road:

Incorrect:

def carArrived(self, carId, roadId, direction, turnGreen, crossCar):
    with self.lock:
        self.road = roadId
        turnGreen()  # Wrong: calls even when light is already green
        crossCar()

This violates the requirement that turnGreen() should only be called when actually changing the light from red to green.

4. Over-complicating with Multiple Locks or Conditions

Some implementations try to use separate locks for each road or complex condition variables:

Over-complicated:

def __init__(self):
    self.lock_a = Lock()
    self.lock_b = Lock()
    self.condition = Condition()
    # Unnecessarily complex!

Better: A single lock is sufficient and cleaner since only one road can be green at a time anyway.

5. Not Initializing the Road State Properly

Forgetting to initialize self.road or setting it to an invalid value:

Incorrect:

def __init__(self):
    self.lock = Lock()
    # Missing: self.road initialization
    # Or wrong: self.road = 0 or self.road = None

This would cause the first car from Road A to unnecessarily call turnGreen() even though Road A already has the green light initially.