How do you approach Traffic Light Controller?

The light state is shared mutable state - the canonical concurrency answer is a mutex around the carArrived path.

What is the time complexity of Traffic Light Controller?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Traffic Light Controller?

Re-checking a condition with if instead of while after waiting. Spurious wakeups are real. Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock. Assuming statements execute in program order without a barrier, a volatile read, or an atomic.

gitGood.dev

← Back to problems

Traffic Light Controller

HardOperating Systems

Description

**Concurrency design problem (paper-only).** Threading is not available; the auto-grader validates a simulation of the mutual-exclusion contract. There is an intersection of two roads. Road `A` runs north-south (direction `1`), road `B` runs east-west (direction `2`). At any moment, only **one** road can have the green light. Cars arrive at the intersection from one of the two directions; if their direction currently has the green light they pass immediately, otherwise the light flips (preempting one car of "switch overhead") before they pass. Implement `carScheduling(cars)` where `cars` is an array of integers `1` or `2` (the direction of each arriving car, in arrival order). Initially the green light is on direction `1`. Return the total number of light-switch events (every time the controller toggles directions). The interview-grade answer uses a single mutex around the light state so the critical section is atomic.

Example 1

Input: cars = [1,1,2,2,1]

Output: 2

Explanation: Light starts at direction 1. Cars 1,1 pass freely. Car 2 forces a switch (1 switch). Car 2 passes freely. Car 1 forces another switch (2 switches total).

Example 2

Input: cars = [1,1,1]

Output: 0

Example 3

Input: cars = [2,1,2,1]

Output: 4

Constraints

- 1 <= cars.length <= 10^4 - cars[i] in {1, 2}

Traffic Light Controller: approach, complexity and pitfalls

A hard concurrency problem, graded against 6 test cases (3 of them hidden).

The pattern: Concurrency

Coordinating threads with locks, semaphores, and condition variables.

Reach for it when you see: Ordering guarantees between threads, bounded buffers, or classic synchronisation puzzles.

More Concurrencyproblems →

If you are stuck

Show the 3-step hint ladder

The light state is shared mutable state - the canonical concurrency answer is a mutex around the carArrived path.
For the simulation: track current direction. For each car, if direction differs from current, increment switch count and update current.
Initial direction is 1.

The optimal approach

Show the approach: Real concurrent design

```

class TrafficLight:

current: int = 1 # 1 = N-S green, 2 = E-W green

lock: Mutex

def carArrived(self, roadId, turnGreen, crossCar):

with self.lock:

if self.current != roadId:

turnGreen()

self.current = roadId

crossCar()

```

The mutex makes the read-modify-write of `current` atomic. Without it, two cars from different directions could both observe `current != roadId`, both turn green, and both proceed - a collision.

We do not need separate per-direction queues; mutual exclusion alone is enough. Throughput could be improved with a fairness scheme (e.g. let up to K cars from the active direction through before honouring a waiting opposite car) but that's an extension.

Why it's interesting: the trap candidates fall into is using two separate mutexes (one per direction) - that allows the cross-direction violation. The whole intersection is one critical section.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Concurrency mistakes

These apply to the pattern as a whole, not just this problem.

Re-checking a condition with `if` instead of `while` after waiting. Spurious wakeups are real.
Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock.
Assuming statements execute in program order without a barrier, a volatile read, or an atomic.