1279. Traffic Light Controlled Intersection

EasyConcurrency
Leetcode Link

Problem Description

The problem describes an intersection of two roads, Road A and Road B. Cars can travel on Road A from North to South (direction 1) and from South to North (direction 2), while on Road B, they can travel from West to East (direction 3) and from East to West (direction 4). There is a traffic light for each road. The key aspects are:

  • A green light allows cars to cross the intersection along that road.
  • A red light means cars cannot cross and must wait for a green light.
  • The lights for the two roads cannot be green simultaneously. When one is green, the other must be red.
  • Initially, Road A has a green light and Road B has a red light.
  • The traffic lights should avoid causing a deadlock, where cars are perpetually waiting to cross.

Cars arriving at the intersection are represented with a carId and roadId. The roadId signifies which road the car intends to use. The direction of the car is indicated by direction. Two functions are provided - turnGreen, which turns the traffic light green on the current road, and crossCar, allowing the car to cross the intersection.

The core challenge is to design a system using these components to ensure cars can cross the intersection without deadlocks.

Intuition

To ensure a deadlock-free traffic system, we need to manage the traffic lights in a way that each car will eventually be able to cross the intersection. The logic should meet two main criteria:

  • No two cars from different roads should cross at the same time.
  • Changing the traffic light to green on a road when it is already green is unnecessary and should be avoided.

The solution uses a lock mechanism via the Lock class from the threading module to prevent the intersection state from being changed by multiple cars at the same time, ensuring consistency in traffic light changes and crossings. The idea is to synchronize the access to the traffic light state, so at any moment, only one car can influence it.

A TrafficLight object maintains the state of the traffic light for both roads with a variable, starting with road A as green (road = 1). When a car arrives at the intersection (carArrived method), we acquire the lock to prevent other cars from entering the intersection. Then, we check if the car's road ID is the same as the road currently allowed to cross. If not, we call turnGreen() to change the traffic light to green for this car's road and update the self.road attribute. Then, we let the car cross by calling crossCar() and release the lock so the next car can proceed. This mechanism ensures that the cars will cross one at a time, changing the traffic light only when necessary and thus preventing deadlocks.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The solution utilizes a simple concurrency control mechanism with a Lock from the threading module in Python, ensuring that the state of the traffic light is manipulated by only one car at a time.

Here's the step-by-step implementation:

  1. An instance of TrafficLight is initialized with:

    • A Lock object to control concurrent access to the traffic light state.
    • An integer field road, initialized to 1, indicating that road A is green at the start.

  2. When a car arrives, it invokes the carArrived method with its carId, roadId, the direction it wants to travel, and two callback functions: turnGreen and crossCar.

  3. The first action within carArrived is to acquire the lock by calling self.lock.acquire(). This step ensures that only one car can execute the following code at any given time, effectively serializing cross-intersection operations.

  4. Once inside the critical section, the method proceeds to check if the traffic light needs to be changed. This is determined by comparing the roadId of the car with the road attribute of the TrafficLight instance. If they are not equal, it means the car is on the road that currently has a red light and the light needs to be changed to green. This is performed by:

    • Updating self.road to roadId of the current car, indicating which road is now green.
    • Calling the turnGreen() function to simulate the traffic light changing to green for that road.

  5. After ensuring the road is green for the car, the crossCar() function is called, allowing the car to cross the intersection.

  6. Finally, before exiting, the carArrived method releases the acquired lock by calling self.lock.release(), allowing the next car to proceed with its attempt to cross the intersection.

The Lock effectively serves as a gatekeeper to ensure the intersection's state integrity is maintained, eliminating the chances of Deadlock by serializing the changes to the traffic lights and the crossing of cars. This design is simplistic but sufficient for the stated problem requirements, showcasing a classic use of concurrency primitives such as mutexes (locks) to ensure thread-safe operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Example Walkthrough

Let's illustrate the solution approach with a hypothetical situation involving four cars arriving at the intersection. Assume that initially, Road A has a green light and Road B has a red light as per the rules.

  1. Car 1 arrives, with carId = 1, roadId = 1 (Road A), and direction = 1 (North to South).

    • carArrived is called for Car 1.
    • The lock is acquired, and it's checked against the traffic light's state.
    • Since Car 1 is on Road A, which is already green, no traffic light change is necessary.
    • crossCar is called for Car 1, allowing it to cross.
    • The lock is released.

  2. Car 2 arrives shortly after, with carId = 2, roadId = 1 (Road A), and direction = 2 (South to North).

    • carArrived is called for Car 2.
    • Car 2 successfully acquires the lock as Car 1 has released it.
    • The traffic light is still green for Road A.
    • crossCar is called for Car 2, allowing it to cross.
    • The lock is released.

  3. Car 3 arrives next, with carId = 3, roadId = 2 (Road B), and direction = 3 (West to East).

    • carArrived is called for Car 3.
    • The lock is acquired.
    • The traffic light check reveals a change is needed since Car 3 is on Road B, and the current green light is for Road A.
    • The road attribute is updated to 2.
    • turnGreen() is called, setting the traffic light green for Road B.
    • crossCar is called for Car 3, and it crosses the intersection.
    • The lock is released.

  4. Finally, Car 4 approaches, with carId = 4, roadId = 2 (Road B), and direction = 4 (East to West), while the light is still green on Road B thanks to Car 3.

    • The lock is acquired by the carArrived method for Car 4.
    • Since the light is already green for Road B, no light change is needed.
    • crossCar is called for Car 4 to cross.
    • The lock is finally released.

This walkthrough demonstrates how the lock mechanism ensures that each car's arrival is dealt with one by one, allowing for proper management of the traffic lights and safe crossing of the intersection without deadlocks. The lights change only when necessary, and multiple cars on the same road can take advantage of the light being green without requiring the light to be repeatedly changed.

Solution Implementation

1from threading import Lock
2from typing import Callable
3
4class TrafficLight:
5    def __init__(self):
6        self.lock = Lock()  # lock to control concurrency and avoid race condition
7        # state to keep track of which road is green
8        # initially, road 1 is set to green
9        self.green_road_id = 1
10
11    def carArrived(
12        self,
13        carId: int,  # identifier of the car
14        roadId: int,  # identifier of the road the car is on; can be 1 or 2
15        direction: int,  # direction the car is traveling in
16        turnGreen: Callable[[], None],  # function to call to turn the light green
17        crossCar: Callable[[], None],   # function to call to let the car cross
18    ) -> None:
19        # acquire lock to ensure exclusive access to the light
20        with self.lock:
21            # If the car's road ID is different from the current green road,
22            # change the traffic light to this car's road
23            if self.green_road_id != roadId:
24                self.green_road_id = roadId  # update the green road ID
25                turnGreen()  # call the method to turn the traffic light green
26
27            crossCar()  # allow the car to cross the intersection
28            # lock is released automatically when the 'with' block ends
29
1class TrafficLight {
2    private int currentRoadId = 1; // Variable to store which road has the green light
3
4    public TrafficLight() {
5        // Constructor - no initialization needed as we start with road 1 by default
6    }
7
8    // Synchronized method to allow cars to arrive at the intersection without race conditions
9    public synchronized void carArrived(
10        int carId,        // ID of the car arriving at the intersection
11        int roadId,       // ID of the road the car is on. Can be 1 (road A) or 2 (road B)
12        int direction,    // Direction of the car, not used in the current context
13        Runnable turnGreen,   // Runnable to turn light to green on the car's current road
14        Runnable crossCar     // Runnable to allow the car to cross the intersection
15    ) {
16        // Check if the road that the car wants to use does not have green light
17        if (roadId != currentRoadId) {
18            turnGreen.run();       // Turn the light green for the current road
19            currentRoadId = roadId; // Update the current road ID to the car's road ID
20        }
21      
22        // Allow the car to cross the intersection
23        crossCar.run();
24    }
25}
26
1#include <mutex>
2#include <functional>
3
4class TrafficLight {
5private:
6    int currentRoadId = 1; // Variable to store which road has the green light
7    std::mutex mtx; // Mutex to protect shared resources and prevent race conditions
8
9public:
10    // Constructor - no initialization needed as we start with road 1 by default
11    TrafficLight() {}
12
13    // Synchronized method to allow cars to arrive at the intersection without race conditions
14    void carArrived(
15        int carId,             // ID of the car arriving at the intersection
16        int roadId,            // ID of the road the car is on. Can be 1 (road A) or 2 (road B)
17        int direction,         // Direction of the car, not used in the current context
18        std::function<void()> turnGreen,    // Function to turn light to green on the car's road
19        std::function<void()> crossCar      // Function to allow the car to cross the intersection
20    ) {
21        {
22            // Locking the mutex to ensure exclusive access to the shared variable currentRoadId
23            std::lock_guard<std::mutex> lock(mtx);
24
25            // Check if the road that the car wants to use does not have green light
26            if (roadId != currentRoadId) {
27                turnGreen();             // Turn the light green for the current road
28                currentRoadId = roadId;  // Update the current road ID to the car's road ID
29            }
30        } // Mutex is released automatically when lock goes out of scope
31
32        // Allow the car to cross the intersection
33        crossCar();
34    }
35};
36
1// Variable to store the ID of the current road with a green light
2let currentRoadId = 1;
3
4// Function to simulate the car arriving at the intersection
5// Ensures synchronization to prevent race conditions
6function carArrived(
7  carId: number,          // ID of the car arriving at the intersection
8  roadId: number,         // ID of the road the car is on. Can be 1 (for road A) or 2 (for road B)
9  direction: number,      // Direction of the car, not currently used
10  turnGreen: () => void,  // Function to invoke to turn the traffic light green for the current road
11  crossCar: () => void    // Function to invoke to allow the car to cross the intersection
12): void {
13  // The synchronization mechanism provided by the `synchronized` keyword in Java is
14  // not directly available in TypeScript/JavaScript. We would typically need to manage
15  // concurrency with Promise chains, Async/Await, or other synchronization primitives.
16
17  // Simulate synchronization lock to ensure one car processes at a time
18  // (This is conceptual, actual implementation would require additional code.)
19  synchronized(() => {
20    if (roadId !== currentRoadId) {
21      turnGreen(); // If the car's road ID differs from the current, turn the light to green
22      currentRoadId = roadId; // Update the current road ID
23    }
24
25    crossCar(); // Once the traffic light is green, the car can cross the intersection
26  });
27}
28
29// Synchronization helper function (Note: This is a placeholder as JavaScript/TypeScript
30// does not directly support the synchronized concept out-of-the-box)
31function synchronized(action: () => void): void {
32  // Enter synchronization lock
33  action();
34  // Exit synchronization lock
35}
36
Not Sure What to Study? Take the 2-min Quiz：

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Time and Space Complexity

Time Complexity

The time complexity of the carArrived method is O(1). This is because there are no loops or recursive calls that depend on the size of the input. Each function call to turnGreen() and crossCar() is considered a constant time operation. Acquiring and releasing a lock is also a constant time operation.

Space Complexity

The space complexity of the TrafficLight class is O(1). It uses a fixed amount of space: one lock and one integer variable, regardless of the number of times the carArrived method is called or the number of car objects interacting with the system.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫