Traffic Light Controlled Intersection - Practice Coding Problems

Traffic Light Controlled Intersection - Problem

Concurrency Easy

There is an intersection of two roads. Road A allows cars to travel from North to South in direction 1 and from South to North in direction 2. Road B allows cars to travel from West to East in direction 3 and from East to West in direction 4.

There is a traffic light located on each road before the intersection. A traffic light can either be green or red:

Green means cars can cross the intersection in both directions of the road
Red means cars in both directions cannot cross the intersection and must wait

The traffic lights cannot be green on both roads at the same time. Initially, the traffic light is green on road A and red on road B.

Design a deadlock-free traffic light controlled system. Implement the function carArrived(carId, roadId, direction, turnGreen, crossCar) where:

carId is the id of the car that arrived
roadId is the id of the road (1 for road A, 2 for road B)
direction is the direction of the car
turnGreen is a function to turn the traffic light green on the current road
crossCar is a function to let the current car cross the intersection

Constraints: Your solution must avoid deadlock and ensure only cars from the same road cross simultaneously.

Input & Output

Example 1 — Basic Car Flow

$ Input: Car 1 arrives on road A (direction 1), Car 2 arrives on road A (direction 2)

› Output: Both cars cross since road A is initially green

💡 Note: Road A starts with green light. Both cars from road A can cross without switching lights.

Example 2 — Light Switch Required

$ Input: Car 1 on road A crosses, then Car 2 arrives on road B (direction 3)

› Output: Car 2 turns light green for road B, then crosses

💡 Note: Car 2 needs to switch from road A (green) to road B (green), making road A red.

Example 3 — Multiple Cars Same Road

$ Input: Car 1, Car 2, Car 3 all arrive on road B simultaneously

› Output: Light switches to road B, all three cars cross together

💡 Note: Multiple cars from same road can cross simultaneously once that road has green light.

Constraints

1 ≤ carId ≤ 1000
roadId ∈ {1, 2} (1 for road A, 2 for road B)
direction ∈ {1, 2, 3, 4}
Initially road A is green, road B is red
Only one road can be green at any time

Visualization

Tap to expand

Understanding the Visualization

Initial State

Road A green, Road B red, cars can arrive on either road

Light Control

Switch lights when car from different road needs to cross

Safe Crossing

Cars cross intersection without collision

Key Takeaway

🎯 Key Insight: Use mutex locks to ensure mutual exclusion between roads

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to use mutual exclusion to ensure only one road can have a green light at any time. The mutex-based approach provides thread-safe coordination between roads. Best approach uses locks with state tracking. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Semaphore-Based Control	O(1)	O(1)	Use semaphores for better concurrent car handling within same road
Basic Synchronization	O(1)	O(1)	Use simple locks to ensure mutual exclusion between roads

Semaphore-Based Control — Algorithm Steps

Step 1: Acquire semaphore for road access
Step 2: Check and switch lights if needed
Step 3: Allow multiple cars from same road to cross
Step 4: Release semaphore when done

Visualization

Tap to expand

Step-by-Step Walkthrough

Acquire Semaphore

Car gets permission to enter road section

Switch Light

Change light if needed, track cars on road

Multiple Cars Cross

Cars from same road can cross together

Code -

solution.c — C

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

typedef struct {
    pthread_mutex_t roadMutex;
    sem_t semaphoreA;
    sem_t semaphoreB;
    int currentRoad;
    int carsOnRoad;
} TrafficLight;

TrafficLight* createTrafficLight() {
    static TrafficLight tl;
    pthread_mutex_init(&tl.roadMutex, NULL);
    sem_init(&tl.semaphoreA, 0, 1);
    sem_init(&tl.semaphoreB, 0, 1);
    tl.currentRoad = 1;
    tl.carsOnRoad = 0;
    return &tl;
}

void carArrived(TrafficLight* tl, int carId, int roadId, int direction,
               void (*turnGreen)(), void (*crossCar)()) {
    sem_t* semaphore = (roadId == 1) ? &tl->semaphoreA : &tl->semaphoreB;
    
    sem_wait(semaphore);
    
    pthread_mutex_lock(&tl->roadMutex);
    if (tl->currentRoad != roadId) {
        turnGreen();
        tl->currentRoad = roadId;
    }
    tl->carsOnRoad++;
    pthread_mutex_unlock(&tl->roadMutex);
    
    crossCar();
    
    pthread_mutex_lock(&tl->roadMutex);
    tl->carsOnRoad--;
    pthread_mutex_unlock(&tl->roadMutex);
    
    sem_post(semaphore);
}

int main() {
    TrafficLight* trafficLight = createTrafficLight();
    printf("Enhanced TrafficLight system initialized\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Each car operation still takes constant time

✓ Linear Growth

Space Complexity

O(1)

Uses semaphore and state variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Semaphore-Based Control — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler