## Algorithmic analysis / code review: Dispatcher for memory-constrained scheduling You are given a single-threaded in-memory **dispatcher** that reacts to two kinds of API calls: ### Downstream (storage/table) requests - `CreateTable(tableId, memoryRequired)` - `ResizeTable(tableId, newMemoryRequired)` ### Upstream (mini-orchestrator) capabilities - `CreateWorkload(machineId, tableId)` (place a table/workload on a machine) - `MoveWorkload(tableId, fromMachineId, toMachineId)` ### Problem The dispatcher must maintain the state of: - A set of **machines** with fixed memory capacities. - A set of **tables/workloads** each requiring some amount of memory. - A mapping of which table is placed on which machine. When a table is created or resized, the dispatcher should: 1. Check whether the current machine (if already placed) still has enough free memory. 2. If not, choose a destination machine and **move** the workload. 3. If the table is new, choose a machine and **place** it. You are handed a correct but inefficient implementation. ### Tasks 1. Analyze the **time complexity** of the naive approach (typical pitfalls: scanning all machines, repeated recomputation of free memory). 2. Propose improved **data structures** to support fast: - lookup by `tableId` and `machineId` - choosing a machine with enough free memory - updating free memory after moves/resizes 3. Propose a reasonable **scheduling policy** (e.g., first-fit/best-fit) and discuss tradeoffs. ### Constraints / clarifications - No external database. - No multithreading/concurrency concerns. - Focus on algorithmic efficiency, correctness, and maintainability. - Consider edge cases (missing table, downsizing, exact-fit, fragmentation).