1279. Traffic Light Controlled Intersection
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 76.2%
Problem Breakdown
The problem involves designing a traffic light control system for an intersection with two roads. Cars arrive at the intersection from different directions and need to cross safely without causing deadlocks. The traffic lights on each road can be either green or red, but they cannot both be green simultaneously.
Inputs:
carId: Unique identifier for each car.roadId: Identifier for the road the car is traveling on (1 or 2).direction: Direction of travel for the car (1 to 4).turnGreen: Function to turn the traffic light green on the current road.crossCar: Function to allow the car to cross the intersection.
Outputs:
- The function should ensure that cars from different roads do not cross simultaneously, avoiding deadlocks. It should also handle the transition of the traffic light between roads correctly.
Implicit Constraints/Edge Cases:
- Initially, the traffic light is green on road A and red on road B.
- If a car arrives on a road where the light is already green, it can cross immediately.
- If a car arrives on a road where the light is red, the light must turn green before the car can cross.
Intuition
A brute-force approach would involve checking each car’s arrival and manually managing the traffic lights. However, this would be inefficient and error-prone due to potential deadlocks and race conditions.
The key insight is to use a mutex (or lock) to ensure that only one road has its light green at any given time. This prevents cars from different roads from crossing simultaneously, thus avoiding deadlocks.
Approach
- Mutex Initialization: Use a mutex to control access to the traffic light.
- Car Arrival Handling:
- Acquire the lock when a car arrives.
- Check if the current road’s light is green.
- If not, turn the light green for the current road using
turnGreen. - Allow the car to cross the intersection using
crossCar. - Release the lock after the car has crossed.
This approach ensures that only one road can have its light green at any time, preventing cars from different roads from crossing simultaneously.
Complexity Analysis
- Time Complexity: O(1) for each car’s arrival and handling. The mutex operations are assumed to be constant time.
- Space Complexity: O(1), as we only use a single mutex for synchronization.
Solution
import threading
class TrafficLight:
def __init__(self):
self.lock = threading.Lock()
self.current_green_road = 1 # Initially, road A is green
def carArrived(
self,
carId: int, # ID of the car
roadId: int, # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)
direction: int, # Direction of the car
turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road
crossCar: 'Callable[[], None]' # Use crossCar() to make car cross the intersection
) -> None:
with self.lock:
if self.current_green_road != roadId:
turnGreen()
self.current_green_road = roadId
crossCar()
Edge Cases Handled
- Initial State: The traffic light starts green on road A, as specified.
- Concurrent Cars: Multiple cars arriving simultaneously are handled by the mutex, ensuring that only one car crosses at a time.
- Light Transition: If a car arrives on a road with a red light, the light is turned green before the car crosses.
- Single Road Traffic: If all cars arrive from the same road, they can cross without any light transitions.