We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Traffic Light Controlled Intersection

Number: 1410

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

There is an intersection controlled by two traffic lights – one for Road A (north–south) and one for Road B (east–west). Initially, the light on Road A is green and on Road B is red. Cars arrive from one of the roads with a given direction. A car can cross the intersection only if its road’s light is green. If a car arrives on a road that currently is red, then the car must turn the light green on its road (which automatically turns the other road’s light red) before crossing. Cars on the same road may cross concurrently, but cars from different roads must never cross at the same time. The task is to design the system so no deadlock occurs and the call to turnGreen is made only when needed (i.e. it must not be called if the light is already green for that road).

Key Insights

  • Use a global variable (protected by a mutex/lock) to track which road currently has a green light.
  • When a car arrives, check if its road’s light is already green.
  • If not, call turnGreen to switch the light (ensuring it is called only once per switch) and update the global state.
  • Protect the check-and-update sequence with a mutex so that even concurrent calls maintain consistency.
  • Cars on the same road can cross concurrently while cars from the opposite road must wait until the light switches.

Space and Time Complexity

Time Complexity: O(1) per car (the operations under lock are constant time) Space Complexity: O(1) (only a few shared variables and synchronization primitives are used)

Solution

The solution maintains a shared variable, currentGreenRoad, which is initially set to road A (represented as 1). In the carArrived function, we acquire a lock to check if the arriving car’s road is already green. If not, we call turnGreen to switch the light and update currentGreenRoad before letting the car cross. The mutex guarantees that only one thread updates the state at a time, ensuring that turnGreen is never called redundantly and that cars from different roads do not cross simultaneously.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed inline comments.

import threading

# Shared variable representing the current road with green light.
# 1 means Road A (green), 2 means Road B (if roads are labeled as such).
current_green = 1
# Create a mutex to protect access to current_green.
lock = threading.Lock()

def carArrived(carId, roadId, direction, turnGreen, crossCar):
    global current_green
    # Acquire lock to check and possibly update the current green light.
    with lock:
        if current_green != roadId:
            # The current road does not have a green light.
            # Call turnGreen to switch and update the global state.
            turnGreen()  # Switches traffic light to roadId.
            current_green = roadId
    # Call crossCar to let the car cross the intersection.
    crossCar()
    
# Note: In an actual concurrency testing environment, turnGreen and crossCar
# are provided functions that output the corresponding actions.
← Back to All Questions