Katkat
Back

Schedule Incremental Labeling Tasks

OpenAIMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to design an incremental task scheduler that balances workload across a pool of annotators while maintaining fairness and deterministic state transitions.

Problem Description

You are building a task scheduler for an incremental labeling pipeline. You have a pool of N annotators and a stream of incoming labeling tasks. Each task has a priority level (1 to 10) and a difficulty score. Annotators have a current load (sum of difficulties of their assigned tasks).

Your goal is to implement a scheduler that assigns incoming tasks to the annotator with the lowest current load. If multiple annotators have the same minimum load, assign the task to the annotator with the lowest ID (0 to N-1) to ensure deterministic behavior.

Implement a class TaskScheduler with the following methods:

assign_task(task_id: int, difficulty: int) -> int

  • Assigns the task to the most appropriate annotator based on the rules above.
  • Updates the annotator's load and returns the annotator's ID.

get_annotator_load(annotator_id: int) -> int

  • Returns the current total difficulty load of a specific annotator.

Constraints

  • N (number of annotators) is up to 10^5.
  • Number of tasks is up to 10^6.
  • difficulty is a positive integer.

Example

# 3 annotators available (IDs 0, 1, 2)
scheduler = TaskScheduler(3)

# Assign tasks
scheduler.assign_task(101, 10) # Returns 0 (load: 10)
scheduler.assign_task(102, 5)  # Returns 1 (load: 5)
scheduler.assign_task(103, 5)  # Returns 2 (load: 5)
scheduler.assign_task(104, 2)  # Returns 1 (load: 7)

Edge Cases

  • All annotators start with a load of 0.
  • Tie-breaking is critical when many annotators are idle.
  • Consider efficiency; the assignment must be faster than linear search.

Hints

Hint 1

To efficiently find the minimum load annotator, consider using a min-heap.

Hint 2

Since the heap stores pairs of (load, annotator_id), how can you update the state when an annotator's load changes?

Hint 3

If you cannot remove an arbitrary element from a standard heap, use a lazy-deletion strategy where you ignore outdated entries.

Follow-up questions

  • How would you modify your design if annotators have different 'speed' multipliers, affecting how quickly their load decreases over time?
  • How can you ensure the scheduler state is persistent and can be recovered if the service restarts?
  • What changes are needed if tasks have deadlines, meaning an annotator must be chosen based on both current load and the ability to complete the task before the deadline?