Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design algorithms for test scheduling states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Design algorithms for test scheduling

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You have tens of thousands of graphics test cases with inter-test dependencies and hardware/driver constraints. Model this as a graph and design algorithms to detect cycles, produce a valid execution order, and minimize total wall-clock time across N heterogeneous GPU executors. Analyze time/space complexity and discuss heuristics for load balancing.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design algorithms for test scheduling states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Part 1: Detect Cycles, Topologically Order, and Greedily Schedule GPU Tests

You have n graphics tests labeled 0 through n - 1. Each test has a base duration, a required GPU type or wildcard *, and a minimum driver version. Dependencies are directed edges (a, b), meaning test a must finish before test b can start. You also have heterogeneous GPU executors, each with a GPU type, driver version, and integer speed. A test can run on an executor if the GPU type matches or the test requires *, and the executor driver version is high enough. Runtime on an executor is ceil(base_duration / executor_speed). First detect dependency cycles and produce a deterministic topological order using the smallest available test id first. If acyclic, schedule tests in that topological order. For each test, choose the compatible executor that gives the earliest finish time, breaking ties by earlier start time and then smaller executor id. This is a deterministic greedy list-scheduling heuristic, not a guaranteed globally optimal scheduler.

Constraints

  • 0 <= n <= 20000
  • len(durations) = len(requirements) = len(min_drivers) = n
  • durations[i] >= 1 for every test i
  • executor_speeds[i] >= 1 for every executor i
  • Dependencies contain valid test ids; duplicate dependency edges should be ignored
  • The exact globally optimal heterogeneous scheduling problem is NP-hard, so this problem asks for the specified deterministic greedy heuristic

Examples

Input: (0, [], [], [], [], ['A'], [1], [1])

Expected Output: [[0, 0], []]

Explanation: No tests means no cycle and a makespan of 0.

Input: (3, [1, 1, 1], ['*', '*', '*'], [0, 0, 0], [(0, 1), (1, 2), (2, 0)], ['A'], [1], [1])

Expected Output: [[1, -1], []]

Explanation: The dependencies form a directed cycle.

Hints

  1. Use Kahn's algorithm with a min-heap to detect cycles and get a deterministic topological order.
  2. When scheduling a test, its earliest possible start on an executor is the max of that executor's availability and the finish times of all predecessors.

Part 2: Streaming Topological Sort for Dependency Graphs Too Large for Memory

You are given n graphics tests labeled 0 through n - 1 and dependency edges arriving in batches. Assume the full edge list is too large to store as an adjacency list. Implement a multi-pass streaming topological sort that keeps only O(n) state plus the current ready batch. First scan the stream to count indegrees. Then repeatedly process all currently zero-indegree unprocessed tests in increasing id order, rescan the edge stream, and decrement targets of edges whose source was just processed. If no test is ready before all tests are processed, report a cycle.

Constraints

  • 0 <= n <= 5000 for this coding version
  • All dependency endpoints are valid ids from 0 to n - 1
  • Duplicate edges are allowed and represent repeated copies of the same constraint
  • The algorithm should not build an adjacency list of all edges

Examples

Input: (0, [])

Expected Output: [[0], []]

Explanation: An empty graph is acyclic.

Input: (4, [[(0, 1)], [(1, 2), (2, 3)]])

Expected Output: [[0], [0, 1, 2, 3]]

Explanation: A simple chain is processed one test per pass after the initial source.

Hints

  1. Indegrees can be counted with one pass over the edge batches.
  2. After removing a batch of ready tests, rescan the stream and update only edges whose source was in that removed batch.

Part 3: Validate Production Invariants for a GPU Test Schedule

Production schedulers should assert invariants before dispatching work. Given graphics tests, dependencies, heterogeneous executors, and a proposed schedule, return which invariants are violated. A schedule row is (test_id, executor_id, start, end). Validate test ids, executor ids, dependency ids, exactly-once scheduling, nonnegative nonempty time intervals, executor compatibility, expected runtime, dependency ordering, and non-overlap on each executor.

Constraints

  • 0 <= n <= 20000
  • durations[i] >= 1 and executor_speeds[i] >= 1
  • requirements[i] is either * or a GPU type string
  • Executor array lengths are equal
  • Times are integer wall-clock units
  • For dependency checks involving duplicate scheduled tests, report DUPLICATE_TEST and skip choosing which duplicate should satisfy the dependency

Examples

Input: (0, [], [], [], [], [], [], [], [])

Expected Output: []

Explanation: The empty schedule for an empty test set is valid.

Input: (3, [4, 6, 3], ['A', 'B', '*'], [1, 2, 1], [(0, 2), (1, 2)], ['A', 'B'], [1, 2], [2, 3], [(0, 0, 0, 2), (1, 1, 0, 2), (2, 0, 2, 4)])

Expected Output: []

Explanation: All tests run once, dependencies are satisfied, durations match, and executor intervals do not overlap.

Hints

  1. Build a count of how many times each valid test id appears, plus maps from test id to start and end for tests scheduled exactly once.
  2. Sort intervals by start time per executor to detect overlap in O(k log k) per executor.

Part 4: Analyze a Scheduler Regression Suite for Boundary, Duplicate, and Tie-Breaking Coverage

You are designing tests for a graph-based GPU test scheduler. Given a proposed regression suite, determine whether it contains cases likely to catch three common bug classes: off-by-one boundary bugs, duplicate dependency bugs, and nondeterministic tie-breaking bugs. Each suite case is a graph with n tests and dependency edges. A case covers OFF_BY_ONE if n is 0 or 1, or if valid dependencies in that case touch both boundary ids 0 and n - 1. A case covers DUPLICATE_EDGE if the exact same dependency pair appears at least twice. A case covers TIE_BREAK if, after ignoring duplicate edges, Kahn's algorithm would ever have at least two ready tests at the same time.

Constraints

  • 0 <= len(cases) <= 1000
  • 0 <= n <= 5000 per case
  • Dependency endpoints are valid ids unless the caller is deliberately testing invalid-input behavior; invalid endpoints are ignored for coverage analysis
  • Duplicate edges count for DUPLICATE_EDGE but are ignored when detecting topological tie opportunities

Examples

Input: ([] ,)

Expected Output: [[], ['OFF_BY_ONE', 'DUPLICATE_EDGE', 'TIE_BREAK']]

Explanation: An empty regression suite covers nothing.

Input: ([(1, []), (3, [(0, 1), (1, 2), (1, 2)])],)

Expected Output: [['OFF_BY_ONE', 'DUPLICATE_EDGE'], ['TIE_BREAK']]

Explanation: The singleton graph covers boundary behavior, and the repeated edge covers duplicate handling. The chain has no ready-set tie.

Hints

  1. For tie-breaking coverage, build indegrees using a set of unique edges, then simulate Kahn's algorithm.
  2. Boundary coverage is about exercising ids 0 and n - 1, plus empty or singleton graphs.

Loading coding console...