How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Implement round-robin load balancer | DoorDash Coding Question

Quick Overview

This question evaluates a candidate's ability to implement a strict round-robin load balancer with O(1) average operations while handling concurrent nextServer and update calls, health-check-driven skipping, and failure scenarios, testing competencies in data structures, concurrent programming, and fault-tolerant system behavior.

Implement round-robin load balancer

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement a load balancer that distributes incoming requests across N backend servers in strict round-robin order. Requirements: ( 1) Support addServer(id), removeServer(id), and nextServer() operations in O( 1) average time; ( 2) Skip servers marked unhealthy via markHealthy(id, isHealthy) without breaking round-robin fairness; ( 3) Ensure thread-safe behavior under concurrent calls to nextServer and server updates; ( 4) Discuss failure scenarios (e.g., a server crashes mid-selection) and how you would design health checks; ( 5) Provide unit tests and analyze time/space complexity.

Quick Answer: This question evaluates a candidate's ability to implement a strict round-robin load balancer with O(1) average operations while handling concurrent nextServer and update calls, health-check-driven skipping, and failure scenarios, testing competencies in data structures, concurrent programming, and fault-tolerant system behavior.

Implement a load balancer that distributes requests across backend servers in strict round-robin order, supporting dynamic membership and health toggling. Process a list of `operations` and return a list containing the result of every `next` operation, in order. Each operation is a tuple: - `('add', id)` — register server `id` (appended to the end of the rotation; no-op if it already exists). - `('remove', id)` — remove server `id` from the rotation (no-op if absent). - `('mark', id, isHealthy)` — mark server `id` healthy/unhealthy. Unhealthy servers stay in the rotation but are skipped by `next` (no-op if `id` absent). New servers start healthy. - `('next',)` — return the next healthy server id in round-robin order, then advance. If there is no healthy server, the result is `None`. Round-robin fairness must be preserved across membership and health changes: `next` always continues from where the previous selection left off, scanning forward and wrapping around, skipping unhealthy servers. Return a list with one entry per `next` operation. Example: `[('add','a'),('add','b'),('add','c'),('next',),('next',),('next',),('next',)]` -> `['a','b','c','a']`.

Constraints

0 <= number of operations <= 10^5
Server ids are unique strings; add of an existing id is a no-op
remove/mark of an absent id is a no-op
Newly added servers start healthy
next returns None when there is no currently-healthy server

Examples

Input: ([('add', 'a'), ('add', 'b'), ('add', 'c'), ('next',), ('next',), ('next',), ('next',)],)

Expected Output: ['a', 'b', 'c', 'a']

Explanation: Three healthy servers rotate strictly a->b->c, then wrap back to a.

Input: ([('add', 'a'), ('add', 'b'), ('add', 'c'), ('mark', 'b', False), ('next',), ('next',), ('next',)],)

Expected Output: ['a', 'c', 'a']

Explanation: b is unhealthy and is skipped; rotation is a->c->a while preserving order.

Input: ([('add', 'a'), ('add', 'b'), ('add', 'c'), ('next',), ('remove', 'b'), ('next',), ('next',)],)

Expected Output: ['a', 'c', 'a']

Explanation: First next returns a (pointer now at b). Removing b shifts the rotation; next continues at c, then wraps to a.

Input: ([('next',)],)

Expected Output: [None]

Explanation: No servers registered, so next yields None.

Input: ([('add', 'a'), ('mark', 'a', False), ('next',), ('mark', 'a', True), ('next',)],)

Expected Output: [None, 'a']

Explanation: The only server is unhealthy (None), then made healthy again so next returns a.

Input: ([('add', 'x'), ('add', 'y'), ('next',), ('next',), ('next',), ('next',)],)

Expected Output: ['x', 'y', 'x', 'y']

Explanation: Two servers alternate fairly over four calls.

Input: ([('add', 'a'), ('add', 'b'), ('add', 'c'), ('mark', 'a', False), ('mark', 'b', False), ('mark', 'c', False), ('next',)],)

Expected Output: [None]

Explanation: All servers unhealthy, so next returns None instead of an infinite scan.

Hints

Keep an ordered list of server ids to define rotation order, plus a hash map id -> isHealthy so add/mark are O(1) average.
Store a single integer pointer for the next candidate. On next, scan forward (with modular wraparound) and pick the first healthy server, then set the pointer just past it.
To keep fairness across removals, when you delete a server before the current pointer, decrement the pointer; then re-normalize it modulo the new size so it never points out of range.
Thread-safety in a real system: guard the structure with a single mutex (or a read-write lock favoring next). For O(1) lock-free fairness you can use an atomic counter and a copy-on-write snapshot of the healthy-server array.

Quick Overview