Optimize a dispatcher’s scheduling data structures

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).