sachin-handiekar · March 11, 2026 06:49
diff --git a/gistfile1.txt b/gistfile1.txt
 # Load Balancer — Interview Question

 **Difficulty:** Medium  
 **Topic:** Round Robin · Weighted Routing · HashMap · Design  
 **Time:** 45–60 minutes

 ---

 ## Problem Statement

 You are building the routing layer of a distributed system. Implement a **Load Balancer** that distributes incoming requests across a pool of backend servers.

 The load balancer must support **adding** and **removing** servers dynamically, and must route requests using a **Round Robin** strategy — cycling through available servers in order, one request at a time.

 Each server is identified by a unique string (e.g. `"server-1"`, `"192.168.1.10"`). When `getServer()` is called, return the next server in the rotation. If no servers are available, return `null`.

 ---

 ## Method Signature

 ```java
 void addServer(String serverId)
 void removeServer(String serverId)
 String getServer()
 ```

 You may use a constructor to initialise the load balancer:

 ```java
 LoadBalancer()
 ```

 ---

 ## Constraints

 | Parameter | Value |
 |---|---|
 | Server ID | Non-null, non-empty string |
 | Max servers | Up to 1,000 |
 | Total operations | Up to 100,000 |
 | `getServer()` on empty pool | Return `null` |
 | Duplicate `addServer()` | Ignore silently |
 | `removeServer()` on missing | Ignore silently |

 ---

 ## Test Cases

 ### Test Case 1 — Basic Round Robin

 **Operations:**
 ```
 addServer("A")
 addServer("B")
 addServer("C")
 getServer()  →  "A"
 getServer()  →  "B"
 getServer()  →  "C"
 getServer()  →  "A"   ← wraps around
 getServer()  →  "B"
 ```

 **Expected output:** `["A", "B", "C", "A", "B"]`

 **Explanation:**
 Requests cycle through servers in the order they were added. After reaching the last server, the pointer wraps back to the first.

 ---

 ### Test Case 2 — Remove a Server Mid-Rotation

 **Operations:**
 ```
 addServer("A")
 addServer("B")
 addServer("C")
 getServer()      →  "A"
 removeServer("B")
 getServer()      →  "C"   ← B is gone, next valid is C
 getServer()      →  "A"   ← wraps around, skips B
 getServer()      →  "C"
 ```

 **Expected output:** `["A", "C", "A", "C"]`

 **Explanation:**
 After `B` is removed, the rotation only contains `["A", "C"]`. The pointer continues forward from where it left off — it does not reset to the beginning.

 ---

 ### Test Case 3 — Add Server Dynamically

 **Operations:**
 ```
 addServer("A")
 addServer("B")
 getServer()      →  "A"
 getServer()      →  "B"
 addServer("C")
 getServer()      →  "A"   ← pointer wraps, C joins next cycle
 getServer()      →  "B"
 getServer()      →  "C"   ← C now participates
 ```

 **Expected output:** `["A", "B", "A", "B", "C"]`

 **Explanation:**
 Newly added servers join the end of the rotation and participate from the next full cycle onwards.

 ---

 ### Test Case 4 — Edge: Single Server

 **Operations:**
 ```
 addServer("only-server")
 getServer()   →  "only-server"
 getServer()   →  "only-server"
 getServer()   →  "only-server"
 ```

 **Expected output:** `["only-server", "only-server", "only-server"]`

 **Explanation:**
 With one server, every request goes to the same server. This should not throw or loop infinitely.

 ---

 ### Test Case 5 — Edge: Empty Pool

 **Operations:**
 ```
 getServer()        →  null
 addServer("A")
 getServer()        →  "A"
 removeServer("A")
 getServer()        →  null
 ```

 **Expected output:** `[null, "A", null]`

 **Explanation:**
 `getServer()` must gracefully return `null` when no servers are registered. This tests the candidate's null-handling and boundary awareness.

 ---

 ### Test Case 6 — Edge: Remove Then Re-Add

 **Operations:**
 ```
 addServer("A")
 addServer("B")
 getServer()        →  "A"
 removeServer("A")
 addServer("A")
 getServer()        →  "B"
 getServer()        →  "A"   ← A re-joins at the end
 ```

 **Expected output:** `["A", "B", "A"]`

 **Explanation:**
 Re-adding a previously removed server places it at the **end** of the rotation, not back in its original position.

 ---

 ## Hints

 > *(Share these one at a time only if the candidate is stuck)*

 1. **Hint 1:** What data structure lets you access elements by index and maintain insertion order?
 2. **Hint 2:** You need O(1) lookup to check if a server already exists. Can you combine two data structures?
 3. **Hint 3:** Keep a counter (index) that tracks which server to return next. Use modulo to wrap around.
 4. **Hint 4:** When a server is removed and the index pointer is now out of bounds, what should you do to correct it?

 ---

 ## What a Strong Solution Looks Like

 ```java
 import java.util.ArrayList;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;

 public class LoadBalancer {

    private final List<String> servers = new ArrayList<>();
    private final Set<String> serverSet = new HashSet<>();
    private int index = 0;

    public void addServer(String serverId) {
        if (serverSet.contains(serverId)) return; // ignore duplicates
        servers.add(serverId);
        serverSet.add(serverId);
    }

    public void removeServer(String serverId) {
        if (!serverSet.contains(serverId)) return; // ignore missing
        int pos = servers.indexOf(serverId);
        servers.remove(pos);
        serverSet.remove(serverId);
        // Adjust index so we don't skip the next server
        if (pos < index) {
            index--;
        }
        if (!servers.isEmpty()) {
            index = index % servers.size();
        } else {
            index = 0;
        }
    }

    public String getServer() {
        if (servers.isEmpty()) return null;
        String server = servers.get(index);
        index = (index + 1) % servers.size();
        return server;
    }
 }
 ```

 **Time Complexity:**
 - `addServer()` — O(1) average
 - `removeServer()` — O(N) due to `indexOf` and `remove` on ArrayList
 - `getServer()` — O(1)

 **Space Complexity:** O(N) where N is the number of registered servers

 > **Bonus discussion point:** `removeServer` can be made O(1) by using a `LinkedHashMap` or a doubly-linked list with a map. Ask the candidate if they see the bottleneck.

 ---

 ## Evaluation Rubric

 | Area | What to Look For |
 |---|---|
 | **Round Robin logic** | Correct use of modulo to wrap the index |
 | **Index adjustment on remove** | Handles pointer shift when a server before the current index is removed |
 | **Duplicate handling** | Uses a Set or Map to avoid duplicate entries |
 | **Empty pool** | Returns `null` gracefully without exceptions |
 | **Code quality** | Clean separation of concerns, no magic numbers |
 | **Follow-up** | Can reason about performance trade-offs |

 ---

 ## Follow-Up Questions (Senior Candidates)

 1. **Performance** — *"Your `removeServer` is O(N). How would you redesign the data structure to make it O(1)?"* *(Expected: LinkedHashMap or indexed map)*

 2. **Weighted Round Robin** — *"What if Server A should receive twice as many requests as Server B? How do you extend your design?"* *(Expected: expand the list by weight, or use a counter per server)*

 3. **Health checks** — *"Servers can go down. How would you detect and automatically remove an unhealthy server?"* *(Expected: background thread / heartbeat pings, circuit breaker)*

 4. **Thread safety** — *"Multiple threads are calling `getServer()` simultaneously. What breaks and how do you fix it?"* *(Expected: `synchronized`, `ReentrantLock`, or `AtomicInteger` for the index)*

 5. **Sticky sessions** — *"Some clients must always reach the same server. How would you modify your design to support this?"* *(Expected: consistent hashing or a `clientId → serverId` map)*
	# Load Balancer — Interview Question

	Difficulty: Medium
	Topic: Round Robin · Weighted Routing · HashMap · Design
	Time: 45–60 minutes

	---

	## Problem Statement

	You are building the routing layer of a distributed system. Implement a Load Balancer that distributes incoming requests across a pool of backend servers.

	The load balancer must support adding and removing servers dynamically, and must route requests using a Round Robin strategy — cycling through available servers in order, one request at a time.

	Each server is identified by a unique string (e.g. `"server-1"`, `"192.168.1.10"`). When `getServer()` is called, return the next server in the rotation. If no servers are available, return `null`.

	---

	## Method Signature

	```java
	void addServer(String serverId)
	void removeServer(String serverId)
	String getServer()
	```

	You may use a constructor to initialise the load balancer:

	```java
	LoadBalancer()
	```

	---

	## Constraints

	\| Parameter \| Value \|
	\|---\|---\|
	\| Server ID \| Non-null, non-empty string \|
	\| Max servers \| Up to 1,000 \|
	\| Total operations \| Up to 100,000 \|
	\| `getServer()` on empty pool \| Return `null` \|
	\| Duplicate `addServer()` \| Ignore silently \|
	\| `removeServer()` on missing \| Ignore silently \|

	---

	## Test Cases

	### Test Case 1 — Basic Round Robin

	Operations:
	```
	addServer("A")
	addServer("B")
	addServer("C")
	getServer() → "A"
	getServer() → "B"
	getServer() → "C"
	getServer() → "A" ← wraps around
	getServer() → "B"
	```

	Expected output: `["A", "B", "C", "A", "B"]`

	Explanation:
	Requests cycle through servers in the order they were added. After reaching the last server, the pointer wraps back to the first.

	---

	### Test Case 2 — Remove a Server Mid-Rotation

	Operations:
	```
	addServer("A")
	addServer("B")
	addServer("C")
	getServer() → "A"
	removeServer("B")
	getServer() → "C" ← B is gone, next valid is C
	getServer() → "A" ← wraps around, skips B
	getServer() → "C"
	```

	Expected output: `["A", "C", "A", "C"]`

	Explanation:
	After `B` is removed, the rotation only contains `["A", "C"]`. The pointer continues forward from where it left off — it does not reset to the beginning.

	---

	### Test Case 3 — Add Server Dynamically

	Operations:
	```
	addServer("A")
	addServer("B")
	getServer() → "A"
	getServer() → "B"
	addServer("C")
	getServer() → "A" ← pointer wraps, C joins next cycle
	getServer() → "B"
	getServer() → "C" ← C now participates
	```

	Expected output: `["A", "B", "A", "B", "C"]`

	Explanation:
	Newly added servers join the end of the rotation and participate from the next full cycle onwards.

	---

	### Test Case 4 — Edge: Single Server

	Operations:
	```
	addServer("only-server")
	getServer() → "only-server"
	getServer() → "only-server"
	getServer() → "only-server"
	```

	Expected output: `["only-server", "only-server", "only-server"]`

	Explanation:
	With one server, every request goes to the same server. This should not throw or loop infinitely.

	---

	### Test Case 5 — Edge: Empty Pool

	Operations:
	```
	getServer() → null
	addServer("A")
	getServer() → "A"
	removeServer("A")
	getServer() → null
	```

	Expected output: `[null, "A", null]`

	Explanation:
	`getServer()` must gracefully return `null` when no servers are registered. This tests the candidate's null-handling and boundary awareness.

	---

	### Test Case 6 — Edge: Remove Then Re-Add

	Operations:
	```
	addServer("A")
	addServer("B")
	getServer() → "A"
	removeServer("A")
	addServer("A")
	getServer() → "B"
	getServer() → "A" ← A re-joins at the end
	```

	Expected output: `["A", "B", "A"]`

	Explanation:
	Re-adding a previously removed server places it at the end of the rotation, not back in its original position.

	---

	## Hints

	> (Share these one at a time only if the candidate is stuck)

	1. Hint 1: What data structure lets you access elements by index and maintain insertion order?
	2. Hint 2: You need O(1) lookup to check if a server already exists. Can you combine two data structures?
	3. Hint 3: Keep a counter (index) that tracks which server to return next. Use modulo to wrap around.
	4. Hint 4: When a server is removed and the index pointer is now out of bounds, what should you do to correct it?

	---

	## What a Strong Solution Looks Like

	```java
	import java.util.ArrayList;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Set;

	public class LoadBalancer {

	private final List<String> servers = new ArrayList<>();
	private final Set<String> serverSet = new HashSet<>();
	private int index = 0;

	public void addServer(String serverId) {
	if (serverSet.contains(serverId)) return; // ignore duplicates
	servers.add(serverId);
	serverSet.add(serverId);
	}

	public void removeServer(String serverId) {
	if (!serverSet.contains(serverId)) return; // ignore missing
	int pos = servers.indexOf(serverId);
	servers.remove(pos);
	serverSet.remove(serverId);
	// Adjust index so we don't skip the next server
	if (pos < index) {
	index--;
	}
	if (!servers.isEmpty()) {
	index = index % servers.size();
	} else {
	index = 0;
	}
	}

	public String getServer() {
	if (servers.isEmpty()) return null;
	String server = servers.get(index);
	index = (index + 1) % servers.size();
	return server;
	}
	}
	```

	Time Complexity:
	- `addServer()` — O(1) average
	- `removeServer()` — O(N) due to `indexOf` and `remove` on ArrayList
	- `getServer()` — O(1)

	Space Complexity: O(N) where N is the number of registered servers

	> Bonus discussion point: `removeServer` can be made O(1) by using a `LinkedHashMap` or a doubly-linked list with a map. Ask the candidate if they see the bottleneck.

	---

	## Evaluation Rubric

	\| Area \| What to Look For \|
	\|---\|---\|
	\| Round Robin logic \| Correct use of modulo to wrap the index \|
	\| Index adjustment on remove \| Handles pointer shift when a server before the current index is removed \|
	\| Duplicate handling \| Uses a Set or Map to avoid duplicate entries \|
	\| Empty pool \| Returns `null` gracefully without exceptions \|
	\| Code quality \| Clean separation of concerns, no magic numbers \|
	\| Follow-up \| Can reason about performance trade-offs \|

	---

	## Follow-Up Questions (Senior Candidates)

	1. Performance — "Your `removeServer` is O(N). How would you redesign the data structure to make it O(1)?" (Expected: LinkedHashMap or indexed map)

	2. Weighted Round Robin — "What if Server A should receive twice as many requests as Server B? How do you extend your design?" (Expected: expand the list by weight, or use a counter per server)

	3. Health checks — "Servers can go down. How would you detect and automatically remove an unhealthy server?" (Expected: background thread / heartbeat pings, circuit breaker)

	4. Thread safety — "Multiple threads are calling `getServer()` simultaneously. What breaks and how do you fix it?" (Expected: `synchronized`, `ReentrantLock`, or `AtomicInteger` for the index)

	5. Sticky sessions — "Some clients must always reach the same server. How would you modify your design to support this?" (Expected: consistent hashing or a `clientId → serverId` map)
No results found