0

Data labeling scheduler with prefix-balanced models

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Data labeling scheduler with prefix-balanced models

Companies: OpenAI

Difficulty: Medium

Problem statement

A data labeling platform pairs tasks, AI models and human annotators. IDs are 1-indexed strings: tasks "t1"…"t{totalTask}", models "m1"…"m{totalModel}", humans "h1"…"h{totalHuman}".

An assignment is a triple [task, model, human]: that human labels that task with help from that model. A task may appear in many assignments, with different humans and models.

Part 1: any valid schedule

Implement schedule(totalTask, totalModel, totalHuman, k) -> list[list[str]]. It returns a list of assignments such that:

  1. Every human appears in at least k assignments.
  2. No human is assigned the same task twice.
  3. Every ID is within its range.

Return any valid schedule. If no valid schedule exists, return [].

Constraints: 1 <= totalTask, totalModel, totalHuman <= 100, 0 <= k.

Example: totalTask = 4, totalModel = 1, totalHuman = 3, k = 2. One valid answer:

[["t1","m1","h1"], ["t2","m1","h2"], ["t3","m1","h3"],
 ["t2","m1","h1"], ["t3","m1","h2"], ["t4","m1","h3"]]

k = 5 with totalTask = 4 has no answer, so it returns [].

Part 2: prefix-balanced schedule

Now the order of the list matters. Look at every prefix, meaning the first x assignments for each x >= 1. In every prefix:

  • Per task: for each task, the counts of each model it was used with differ by at most 1. Models used 0 times count as 0.
  • Per human: for each human, the counts of each model they used differ by at most 1, counted the same way.

Implement balanced_schedule(totalTask, totalModel, totalHuman, k). It must meet all of the Part 1 rules plus this one, or return [] if that is impossible.

Example: totalTask = 3, totalModel = 2, totalHuman = 2, k = 2. One valid answer:

[["t1","m1","h1"], ["t1","m2","h2"], ["t2","m2","h1"], ["t2","m1","h2"]]

After the first assignment, t1 has m1:1, m2:0, which is fine. After all four, every task and every human has used each model once.

Part 3 (if time allows): streaming

Humans join one at a time. When a human joins, emit their assignments immediately, and never reorder what you already emitted. The whole stream must stay valid and prefix-balanced after every emission. State the time and the memory your scheduler keeps.

Approach

Nothing here needs search. Each part has a direct construction, and the interview is about seeing it and proving it correct. Most candidates start by writing a validator. That is worth doing, because you will use it to check every later part.

Part 1: any valid schedule. A human may not take the same task twice, so each human needs k different tasks. That is possible exactly when k <= totalTask. When k > totalTask the answer is []. The model can be anything. A brute-force greedy ("for each human, take any task they have not done yet") works. The neater version is a rotation: in round j, human h takes task (h + j) mod T. For a fixed human, j = 0..k-1 gives k different residues because k <= T. The rotation also spreads the work across tasks, so no single task is labeled by everyone. That is the reason to prefer it over "everyone does t1..tk". It takes k rounds of H assignments each, so it is O(H·k).

Part 2: prefix-balanced. For every prefix of the output, each task's model counts must differ by at most 1, and so must each human's. The useful fact: a sequence of model ids is prefix-balanced if it walks the models cyclically from any starting point: a, a+1, a+2, … (mod M). Every window of M consecutive ids is a permutation of all M models, so after L uses each model has been used floor(L/M) or ceil(L/M) times.

So we need one rule that walks cyclically for each task and for each human at the same time. A Latin-square rule does this:

  • Human h takes tasks 0, 1, …, k-1. For the pair (t, h) the model is (t + h) mod M.
  • For a fixed human, the tasks in increasing order give models h, h+1, h+2, …, which is cyclic.
  • For a fixed task, the humans in increasing order give models t, t+1, t+2, …, which is cyclic.

Emit the pairs in task-major order (all humans for t0, then all for t1, …). Each human then sees its tasks in increasing order, and each task sees its humans in increasing order. Both subsequences are cyclic walks, so every prefix is balanced. Tasks that are never used have all-zero counts, which is balanced too.

The rotation from Part 1 fails here. (h + j) mod T wraps from T-1 back to 0, and any model rule tied to the task index jumps at that wrap unless M divides T. Using the first k tasks avoids the wrap. The cost is load spread: tasks t{k+1}.. stay idle. That is a legitimate trade-off to name.

Invariant: the output order is consistent with "per human, task ascending" and "per task, human ascending". Any order with that property works. Task-major and human-major both have it, and Part 3 depends on that.

Code

from collections import defaultdict
from typing import Iterator

Assignment = list[str]


def schedule(total_task: int, total_model: int, total_human: int, k: int) -> list[Assignment]:
    """Part 1: every human gets k distinct tasks; task load is spread round-robin."""
    if k > total_task:
        return []
    out: list[Assignment] = []
    for j in range(k):                      # round j
        for h in range(total_human):
            t = (h + j) % total_task        # rotation: distinct tasks per human
            m = (h + j) % total_model       # any model is legal in part 1
            out.append([f"t{t + 1}", f"m{m + 1}", f"h{h + 1}"])
    return out


def balanced_schedule(total_task: int, total_model: int, total_human: int, k: int) -> list[Assignment]:
    """Part 2: prefix-balanced. Model for (task t, human h) is (t + h) mod M.

    Each human does tasks 0..k-1 in increasing order, and each task is done by
    humans 0..H-1 in increasing order, so both see consecutive model ids.
    """
    if k > total_task:
        return []
    out: list[Assignment] = []
    for t in range(k):                      # task-major order
        for h in range(total_human):
            m = (t + h) % total_model
            out.append([f"t{t + 1}", f"m{m + 1}", f"h{h + 1}"])
    return out


class StreamingScheduler:
    """Part 3: humans arrive one at a time; emit their k assignments immediately.

    Human-major order is also consistent (per human, tasks ascend; per task,
    humans ascend), so the stream stays prefix-balanced after every emission.
    """

    def __init__(self, total_task: int, total_model: int, k: int) -> None:
        if k > total_task:
            raise ValueError("k cannot exceed the number of tasks")
        self.total_model = total_model
        self.k = k
        self.next_human = 0

    def add_human(self) -> Iterator[Assignment]:
        h = self.next_human
        self.next_human += 1
        for t in range(self.k):
            m = (t + h) % self.total_model
            yield [f"t{t + 1}", f"m{m + 1}", f"h{h + 1}"]


def is_valid(sched: list[Assignment], T: int, M: int, H: int, k: int, balanced: bool = False) -> bool:
    seen: set[tuple[str, str]] = set()
    per_human: dict[str, int] = defaultdict(int)
    task_model: dict[str, list[int]] = defaultdict(lambda: [0] * M)
    human_model: dict[str, list[int]] = defaultdict(lambda: [0] * M)
    for t, m, h in sched:
        ti, mi, hi = int(t[1:]), int(m[1:]), int(h[1:])
        if not (1 <= ti <= T and 1 <= mi <= M and 1 <= hi <= H) or (t, h) in seen:
            return False
        seen.add((t, h))
        per_human[h] += 1
        if balanced:
            task_model[t][mi - 1] += 1
            human_model[h][mi - 1] += 1
            if max(task_model[t]) - min(task_model[t]) > 1:
                return False
            if max(human_model[h]) - min(human_model[h]) > 1:
                return False
    return all(per_human[f"h{i}"] >= k for i in range(1, H + 1))

Complexity

  • schedule: O(H·k) time. Output is H·k assignments. O(1) extra space beyond the output.
  • balanced_schedule: O(H·k) time. O(1) extra space beyond the output.
  • StreamingScheduler.add_human: O(k) per human, O(1) per emitted assignment, O(1) state (just the next human id).
  • is_valid: O(N·M) for N assignments when checking balance with max/min over the counts. Use a count-of-counts per entity to make each check O(1). Space is O(N + (T + H)·M).
  • When k > T every function rejects in O(1).

Test cases

  • schedule(3, 1, 2, 2) returns 4 assignments: h1 gets t1, t2 and h2 gets t2, t3. Valid.
  • schedule(1, 1, 1, 1) returns [["t1","m1","h1"]].
  • schedule(2, 3, 3, 3) returns [], because k > totalTask.
  • schedule(4, 2, 3, 0) returns []. That is a valid empty schedule, since every human trivially has at least 0 assignments.
  • balanced_schedule(3, 2, 2, 2) returns [["t1","m1","h1"], ["t1","m2","h2"], ["t2","m2","h1"], ["t2","m1","h2"]]. In every prefix, each task and each human is within 1 across m1/m2.
  • balanced_schedule(5, 1, 3, 4): with one model, balance is automatic. 12 assignments, each human on t1..t4.
  • M > k (for example T=3, M=5, H=2, k=3): each entity uses each model at most once. Balanced.
  • H > T (for example T=2, M=3, H=7, k=2): task t1 sees models m1, m2, m3, m1, m2, m3, m1 across humans. Balanced in every prefix.
  • Exhaustive check: every T <= 7, M <= 5, H <= 7, 0 <= k <= T passes is_valid for all three generators, with balance checked after every single assignment.

Follow-ups

  1. Streaming (reported Part 3). Humans join over time, and you must emit each arrival's assignments without rewriting the past. The Latin rule needs no global knowledge: human h gets (t, (t + h) mod M) for t < k. Human-major emission still keeps per-task human order ascending, so the stream is prefix-balanced after every yield. If tasks stream in instead, swap roles: when task t arrives, emit it to the humans who still need tasks, with model (t + h) mod M.
  2. Spread load across tasks while staying balanced. Ask for every task to be labeled about H·k/T times. Use rotated task windows per human, with the model tied to the human's position in its own window: model = (h + j) mod M. Then order assignments so each task's users arrive with consecutive model ids, or show when the wrap makes that impossible (M not dividing T). A good answer states the trade-off. A strong one gives a bipartite / edge-coloring argument: König's theorem colors a bipartite multigraph with max-degree colors.
  3. Capacities. Human h can take at most cap[h] tasks, and task t needs at least need[t] labels. This becomes bipartite b-matching. Solve it with max-flow (source → humans with capacity cap[h], human → task with capacity 1, task → sink with capacity need[t]) and return [] when the flow falls short. For the sizes here, Dinic runs in milliseconds.
  4. Model eligibility. Some models cannot run on some tasks. Balance then means "within 1 across allowed models". The cyclic walk becomes a walk over each task's allowed list, and in general it may not exist. Discuss detecting infeasibility with a flow or ILP formulation rather than claiming the construction still works.
  5. Distributed / concurrent assignment. Many workers request work at once. Keep per-task and per-human counters in one store and hand out the next (task, model) with an atomic compare-and-set. Assignments must be idempotent by (task, human), so a retry does not double-label.

Interviewer expectations

Mid-level (L4)

  • Spots k > totalTask as the only infeasible case. Produces a correct Part 1 with distinct tasks per human.
  • Writes a validator, or at least checks examples by hand. Handles k = 0.
  • Gets Part 2 working, possibly with hints toward a cyclic model assignment.

Senior (L5)

  • Explains why a cyclic walk mod M is prefix-balanced. Finds the (t + h) mod M rule and proves both the per-task and per-human orders hold.
  • Explains why the Part 1 rotation breaks under Part 2 (the wrap) and names the load-spread trade-off.
  • Handles streaming cleanly with O(1) state, and tests with an exhaustive small-case loop.

Staff (L6+)

  • Generalizes to "any order consistent with both per-entity orders" and uses that to reason about streaming, retries and concurrency.
  • Reframes capacities and eligibility as flow or b-matching. Knows when a closed-form construction stops existing and says how to detect that.
  • Discusses production concerns: idempotent assignment, counters under concurrency, and quality signals such as inter-annotator agreement driving k.

Sign in to comment, vote or remix.