You are implementing a simplified connection router / load balancer for a Jupyter-like multi-tenant server system. There are **N target servers**, indexed from `0` to `N - 1`. Each target server can maintain at most `maxConnectionsPerTarget` concurrent connections. You will implement a small, stateful simulator that processes a sequence of commands and updates internal state accordingly. Assume all commands are processed **sequentially in a single thread**. Connection IDs (`connId`) are arbitrary identifiers (e.g., strings or integers) and are unique per logical client connection. Design an API like the following (you can adapt naming / exact signatures to your chosen language): ```text class ConnectionRouter { ConnectionRouter(int numTargets, int maxConnectionsPerTarget) // Part 1 & 2: connection handling int connect(connId) // Part 3: disconnect handling boolean disconnect(connId) // Part 5: shutdown handling List<connId> shutdown(int targetIndex) } ``` You must support the following behavior, built up in five parts. --- ### Part 1: Basic CONNECT routing (round-robin) Implement `connect(connId)` for the basic case (ignore duplicates, DISCONNECT, and SHUTDOWN for now). - Maintain a **round-robin pointer** over target indices `[0, 1, ..., N-1]`. - When `connect(connId)` is called for a **new** `connId`: - Starting from the current round-robin pointer, scan targets in cyclic order (0 → 1 → ... → N-1 → 0 → ...). - Select the **first target** that is: - not shut down (in Part 1, assume all are up), and - has free capacity (in Part 1, assume effectively unlimited capacity; capacity will be enforced in Part 4). - Assign the connection to that target. - Advance the round-robin pointer to the **next index after the chosen target** (modulo `N`). - Return the chosen `targetIndex`. For now, it is acceptable to assume all connections are unique and never disconnected. You should still design your internal data structures anticipating later parts. --- ### Part 2: Handle duplicate CONNECT calls Extend `connect(connId)` to handle **duplicate connections** with the same `connId`: - If `connId` is **already connected** to some target: - Treat this as a **duplicate CONNECT**. - **Do not** change any internal state: - Do not reassign the target. - Do not change the round-robin pointer. - Do not change any connection counts. - Simply return the **existing target index** for this `connId`. - Only if `connId` is not currently connected should you perform a new assignment using the Part 1 logic. You will therefore need to maintain a mapping from `connId` to its current `targetIndex`. --- ### Part 3: Support DISCONNECT Implement `disconnect(connId)` to explicitly close a connection: - If `connId` is currently connected to some target: - Remove the mapping for this `connId`. - Decrement the active connection count for that target. - Return `true`. - If `connId` is **not** currently connected (unknown or already disconnected): - Do nothing. - Return `false`. The round-robin pointer is **not** affected by disconnect operations. --- ### Part 4: Enforce maxConnectionsPerTarget capacity Now fully enforce per-target capacity via the constructor parameter `maxConnectionsPerTarget`. - Each target can have at most `maxConnectionsPerTarget` active connections at any time. - When a new connection is requested via `connect(connId)` for a previously unseen `connId`: - Use the round-robin scan as in Part 1, but **skip any targets that are already at capacity**. - If you find a target that is **not shut down** and has capacity: - Assign the connection there. - Increment that target's connection count. - Advance the round-robin pointer to just after that target (modulo `N`). - Return that `targetIndex`. - If **all non-shutdown targets are at capacity**, then **ignore the connect request**: - Do **not** create a connection. - Do **not** change any state (including the round-robin pointer). - Return a sentinel value such as `-1` to indicate that no target could be assigned. Duplicate `connect(connId)` calls (where `connId` is already connected) still behave as in Part 2: return the existing target and do not change state. --- ### Part 5: SHUTDOWN target and evict its connections Implement `shutdown(targetIndex)` to temporarily take a target offline and evict all connections currently on that target. - When `shutdown(targetIndex)` is called: 1. If the target is **already shut down**, do nothing and return an empty list. 2. Otherwise: - Mark this target as **unavailable** for future `connect` operations. - Collect **all `connId`s currently assigned to this target**. - For each such `connId`: - Remove its mapping from `connId → targetIndex`. - Decrement the connection count for this target accordingly. - Return the list of evicted `connId`s. - **Eviction order requirement:** - Return evicted connection IDs in the order in which their successful `connect` calls occurred (i.e., connection creation time order on that target). - After a target is shut down: - It must be **skipped** by future `connect` calls (treated as unavailable), regardless of its current connection count. - `disconnect(connId)` should still behave correctly even if the connection was already evicted by a shutdown (i.e., just return `false` when `connId` is not found). You may assume that targets, once shut down, **never come back up** in this problem variant. --- ### Complexity & Data Structures - Let `Q` be the number of operations (CONNECT / DISCONNECT / SHUTDOWN) and `N` be the number of targets. - Aim for **amortized O(1)** or **O(log N)** time per operation. - Discuss and justify the data structures you choose to: - Map `connId` to `targetIndex`. - Track per-target connection counts and the connections assigned to each target in insertion order. - Implement the round-robin selection over available, non-full, non-shutdown targets. Implement the full `ConnectionRouter` with correct behavior across all five parts.