Katkat
Back

Optimize a dispatcher’s scheduling data structures

AirtableSoftware Engineer · Onsite
EasySoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This question evaluates understanding of algorithmic analysis and data-structure design for memory-constrained scheduling, including efficient lookup and update operations for tables and machines and the selection of placement and migration policies, categorized under Software Engineering Fundamentals.

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