Design algorithms for test scheduling

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

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

Example 1

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

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

Example 2

Input: (3, [1, 1, 1], ['*', '*', '*'], [0, 0, 0], [(0, 1), (1, 2), (2, 0)], ['A'], [1], [1])
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

Example 1

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

Explanation: An empty graph is acyclic.

Example 2

Input: (4, [[(0, 1)], [(1, 2), (2, 3)]])
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

Example 1

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

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

Example 2

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

Example 1

Input: ([] ,)
Output: [[], ['OFF_BY_ONE', 'DUPLICATE_EDGE', 'TIE_BREAK']]

Explanation: An empty regression suite covers nothing.

Example 2

Input: ([(1, []), (3, [(0, 1), (1, 2), (1, 2)])],)
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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Model each reachable configuration as a graph state and choose the traversal by edge cost: BFS for unweighted shortest paths, Dijkstra for non-negative weighted paths, or topological DP for DAGs. Track visited states at the correct granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.