Uber·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Uber coding round for a software engineer role, pretty much one meaty algorithmic problem that took up the whole session. The problem was interesting but the pressure to also explain tradeoffs out loud while coding made it trickier than expected.

Questions Asked (1)

Given a list of packages and their build dependencies, produce a valid build order such that every package is built only after its dependencies. If no valid order exists due to a cycle, report that. You also need to explain your algorithm, analyze complexity, handle disconnected components and duplicate dependencies, and compare a BFS in-degree approach with a DFS post-order approach.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is basically topological sort dressed up in a packaging scenario, which I recognized pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the packages as a directed graph where edges represent dependencies, then compute a topological ordering using either Kahn's algorithm (BFS with in-degrees) or DFS post-order. Detect cycles by checking if all nodes are processed (BFS) or if a back edge is found (DFS). Explain both approaches, compare their trade-offs, and discuss how to handle disconnected components and duplicate dependencies.

Pro tip: Emphasize that Kahn's algorithm naturally detects cycles and handles disconnected components, while DFS post-order requires explicit cycle detection and may need to iterate over all nodes. Mention that duplicate dependencies can be handled by using a set for adjacency lists or by ignoring duplicates during in-degree calculation.

1. Clarify and Model the Problem

Restate the problem to ensure understanding: given a list of packages and their dependencies, produce a build order or detect a cycle. Model it as a directed graph where an edge from A to B means A depends on B (or B must be built before A).

2. Choose and Explain the Algorithm

Select either Kahn's algorithm (BFS with in-degrees) or DFS post-order. Explain the steps: for Kahn's, compute in-degrees, enqueue nodes with zero in-degree, process and decrement neighbors; for DFS, perform post-order traversal and reverse the result. Highlight how each handles cycles.

3. Analyze Complexity and Edge Cases

State time and space complexity: O(V+E) for both approaches. Discuss handling of disconnected components (both naturally handle by iterating over all nodes) and duplicate dependencies (use sets or deduplicate during graph construction).

4. Compare BFS and DFS Approaches

Compare Kahn's algorithm and DFS post-order: Kahn's is iterative, easier to detect cycles (if processed count < total nodes), and naturally handles disconnected components; DFS is recursive (may cause stack overflow), requires explicit cycle detection (e.g., coloring), and needs to iterate over all nodes to handle disconnected components.

5. Conclude with Recommendation

Summarize the chosen approach and justify it based on the context (e.g., for Uber's scale, iterative BFS may be preferred to avoid recursion limits). Mention that both are valid and the choice depends on constraints.

Key Points to Mention

Topological sorting using Kahn's algorithm (BFS with in-degree) or DFS post-order.
Cycle detection: in Kahn's, if the number of processed nodes is less than total nodes, a cycle exists; in DFS, use a recursion stack or coloring to detect back edges.
Time and space complexity: O(V+E) for both approaches, where V is number of packages and E is number of dependencies.
Handling disconnected components: both algorithms can process all nodes by iterating over each unvisited node.
Duplicate dependencies: use a set for adjacency lists or deduplicate edges to avoid incorrect in-degree counts.
Trade-offs: Kahn's is iterative and easier to implement for cycle detection; DFS is recursive and may be more intuitive but risks stack overflow and requires careful cycle detection.

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