Katkat

Simulate round-robin package assignment to servers

Capital OneMachine Learning Engineer · Online Assessment

Last 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

  1. The round-robin starts at index 0.
  2. After an assignment to index i, the next search must begin at (i + 1) % n.
  3. 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?