272. Debugging: Round Robin Traffic Router

Debugging: Round Robin Traffic Router

Implement a traffic router that distributes incoming requests across backend servers using round-robin selection.

The router follows the rules described below.

Backend Information

Each backend has:

A unique backendId
A hostname
A port
A state equal to "AVAILABLE" or "UNAVAILABLE"

Round-Robin Rules

Backends are checked in the order in which they were added.
The first request starts searching from the first added backend.
After selecting a backend, the next search starts immediately after that backend.
Searching wraps from the end of the backend list to the beginning.
Backends in the "UNAVAILABLE" state must be skipped.
If every backend is unavailable, return an empty string.
If no backend has been added, return an empty string.
A call must inspect each registered backend at most once.
The round-robin position must persist between method calls.
The requestId does not affect backend selection.
If no available backend is found, the current round-robin position remains unchanged.

Note:

During actual interviews, this question is asked in debugging round. You will already be given an implementation and tests but those will contain logical and compilation defects like below.

You will be required to correct the implementation and change tests only when their expectations contradict the requirements. But for now, implement all methods yourself.

Resetting the round-robin position on every request
Advancing the position incorrectly
Incorrect wrap-around behavior
Returning unavailable backends
Entering an infinite loop when every backend is unavailable
Overwriting existing backends when adding a new backend
Updating the wrong backend state
Using inconsistent or misspelled state values
Incorrect test assertions or test setup

Methods

Add Backend

void addBackend(String backendId, String hostname, int port, String state)

Add a backend to the end of the current round-robin order.

The new backend must not replace any existing backend.
Adding a backend must not reset the current round-robin position.
The supplied state is either "AVAILABLE" or "UNAVAILABLE".

Update Backend State

void updateBackendState(String backendId, String state)

Update the state of the registered backend identified by backendId.

An "AVAILABLE" backend may be selected.
An "UNAVAILABLE" backend must be skipped.
Updating a backend must not reset or otherwise change the round-robin position.
The supplied backendId always identifies an existing backend.

Get Backend

String getBackend(String requestId)

Return the backendId of the next available backend according to the round-robin rules.

Return an empty string if no available backend exists.

Constraints

1 ≤ backendId.length() ≤ 100
1 ≤ hostname.length() ≤ 255
1 ≤ port ≤ 65,535
1 ≤ requestId.length() ≤ 100
state is either "AVAILABLE" or "UNAVAILABLE"
0 ≤ number of added backends ≤ 100,000
Every backendId is unique.
A backend is added at most once.
updateBackendState is called only for an existing backend.
Thread safety is not required.

Examples

Example 1: Basic Round-Robin Selection

TrafficRouter()

addBackend(backendId = "backend-10", hostname = "server10.example.com", port = 8,080, state = "AVAILABLE")

addBackend(backendId = "backend-20", hostname = "server20.example.com", port = 8,081, state = "AVAILABLE")

addBackend(backendId = "backend-30", hostname = "server30.example.com", port = 8,082, state = "AVAILABLE")

getBackend(requestId = "request-101") returns "backend-10".

getBackend(requestId = "request-102") returns "backend-20".

getBackend(requestId = "request-103") returns "backend-30".

getBackend(requestId = "request-104") returns "backend-10" because the search wraps to the beginning.

Example 2: Skip an Unavailable Backend

TrafficRouter()

addBackend(backendId = "east", hostname = "east.example.com", port = 9,001, state = "AVAILABLE")

addBackend(backendId = "central", hostname = "central.example.com", port = 9,002, state = "UNAVAILABLE")

addBackend(backendId = "west", hostname = "west.example.com", port = 9,003, state = "AVAILABLE")

getBackend(requestId = "request-a") returns "east".

getBackend(requestId = "request-b") returns "west" because "central" is unavailable.

getBackend(requestId = "request-c") returns "east".

Example 3: Update Backend Availability

TrafficRouter()

addBackend(backendId = "primary", hostname = "primary.example.com", port = 7,000, state = "AVAILABLE")

addBackend(backendId = "secondary", hostname = "secondary.example.com", port = 7,001, state = "AVAILABLE")

getBackend(requestId = "request-1") returns "primary".

updateBackendState(backendId = "secondary", state = "UNAVAILABLE")

getBackend(requestId = "request-2") returns "primary" because "secondary" is skipped.

updateBackendState(backendId = "secondary", state = "AVAILABLE")

getBackend(requestId = "request-3") returns "secondary".

Example 4: Add a Backend Without Resetting Rotation

TrafficRouter()

addBackend(backendId = "node-1", hostname = "node1.example.com", port = 6,001, state = "AVAILABLE")

addBackend(backendId = "node-2", hostname = "node2.example.com", port = 6,002, state = "AVAILABLE")

getBackend(requestId = "job-1") returns "node-1".

addBackend(backendId = "node-3", hostname = "node3.example.com", port = 6,003, state = "AVAILABLE")

getBackend(requestId = "job-2") returns "node-2".

getBackend(requestId = "job-3") returns "node-3".

Example 5: No Available Backend

TrafficRouter()

addBackend(backendId = "offline-1", hostname = "offline1.example.com", port = 5,001, state = "UNAVAILABLE")

addBackend(backendId = "offline-2", hostname = "offline2.example.com", port = 5,002, state = "UNAVAILABLE")

getBackend(requestId = "request-offline") returns "" because no available backend exists.