NVIDIA·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

Jun 2026

Summary

NVIDIA system design round for a software engineering role. The problem was dense and very GPU-specific, felt more like a research whiteboard than a typical interview.

Questions Asked (1)

You have tens of thousands of graphics test cases with dependencies between them and constraints tied to specific hardware and driver configurations. Model this as a graph, design algorithms to detect cycles and produce a valid execution order, and then figure out how to minimize total wall-clock time across N heterogeneous GPU executors. Walk through time and space complexity and talk about heuristics for load balancing.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This was a lot to unpack.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the test cases as a directed acyclic graph (DAG) with dependencies as edges and hardware constraints as node attributes. Use topological sort to detect cycles and produce a valid order, then apply list scheduling with heuristics like critical path or longest processing time to assign tasks to heterogeneous GPU executors, minimizing makespan. Discuss complexity and trade-offs between optimality and scalability.

Pro tip: Emphasize that in real-world systems, perfect load balancing is NP-hard, so practical solutions use heuristics and may incorporate dynamic feedback from executors to adapt to runtime variability.

1. Model the problem as a graph

Represent test cases as nodes, dependencies as directed edges, and hardware/driver constraints as node labels or edge conditions. This forms a directed graph that may contain cycles if dependencies are invalid.

2. Detect cycles and produce a valid order

Use DFS or Kahn's algorithm to detect cycles. If acyclic, compute a topological ordering that respects dependencies. Discuss time O(V+E) and space O(V+E).

3. Schedule tasks on heterogeneous executors

Model executors as machines with different speeds and capabilities. Use list scheduling: assign tasks in topological order to the executor that minimizes completion time, considering constraints. Discuss heuristics like critical path, longest processing time, and bin packing.

4. Analyze complexity and trade-offs

Topological sort is O(V+E). Scheduling is NP-hard in general; heuristics run in O(V log V + E) or O(V^2). Discuss approximation ratios and scalability for tens of thousands of nodes.

5. Address load balancing and dynamic factors

Mention static vs dynamic scheduling, work stealing, and feedback loops to handle runtime variability. Discuss how to minimize wall-clock time by balancing load and minimizing idle time.

Key Points to Mention

Graph representation: adjacency list for sparse graphs, node attributes for hardware constraints.
Cycle detection: DFS with recursion stack or Kahn's algorithm; handle cycles by reporting or breaking dependencies.
Topological sort: produce linear order; if multiple valid orders, choose one that aids scheduling.
Scheduling heuristics: list scheduling, critical path method, longest processing time first, and bin packing for heterogeneous executors.
Complexity: O(V+E) for graph algorithms; scheduling heuristics often O(V log V + E) or O(V^2); NP-hardness of optimal scheduling.
Load balancing: static vs dynamic, work stealing, and using runtime feedback to adjust assignments.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.