Simulate round-robin package assignment to servers
Capital OneMachine Learning Engineer · Online AssessmentLast updated
This problem tests array indexing manipulation and logic for stateful resource allocation, specifically handling circular queues with dynamic availability constraints.
Problem Statement
You are building a load balancer for a machine learning inference system. You have n servers, indexed from 0 to n-1. Each server i has a fixed maximum capacity c[i]. When a request arrives, you must assign it to the next available server using a round-robin approach. A server is available if its current request count is strictly less than its capacity c[i] and it is not currently marked as 'disabled'.
Implement the class LoadBalancer:
__init__(capacities: List[int]): Initializes the system with a list of server capacities.assign_request() -> int: Assigns the request to the next available server index in a round-robin fashion. If no servers have capacity, return -1.set_server_status(server_id: int, enabled: bool): Updates the status of a server.
Rules
- The round-robin starts at index 0.
- After an assignment to index
i, the next search must begin at(i + 1) % n. - The search for an available server should continue in a circle until an available server is found or all servers have been checked.
Constraints
- 1 <= n <= 10^4
- 1 <= capacity[i] <= 10^6
Example
# Capacities: [2, 1, 2]
lb = LoadBalancer([2, 1, 2])
lb.assign_request() # Returns 0 (current: [1, 0, 0])
lb.assign_request() # Returns 1 (current: [1, 1, 0])
lb.assign_request() # Returns 2 (current: [1, 1, 1])
lb.set_server_status(1, False)
lb.assign_request() # Returns 0 (server 1 is skipped)
Hints
Hint 1
Maintain a pointer variable that tracks the 'last assigned' index to ensure the circular requirement is met.
Hint 2
Use a boolean array to track the enabled status of each server alongside an array to track current usage.
Hint 3
Be careful with the termination condition of the search; ensure you don't enter an infinite loop when all servers are full or disabled.
Follow-up questions
- How would you optimize the `assign_request` function if `n` were 10^6 and most servers were often full?
- If requests had different weights (e.g., resource usage levels), how would your data structure change?
- How would you modify the system to prioritize servers with the most remaining capacity instead of strict round-robin?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.