Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediateRejected

Apr 2026

Summary

Uber SWE technical phone screen with a single graph/topological sort problem. Felt decent about my solution but got the 'we're moving forward with another candidate' email a week later.

Questions Asked (1)

Given a target package and an API that returns the direct dependencies of any package, output a valid build order so that all dependencies are built before the target. Return empty or throw an error if a cycle exists.

Algorithms & Data StructuresAPI & Integrations

Author's notes

The twist is you don't get the full graph upfront.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a directed graph where nodes are packages and edges represent dependencies, then perform a topological sort to determine a valid build order. Use DFS with cycle detection or Kahn's algorithm, ensuring all dependencies are built before the target. Return the order or signal a cycle if detected.

Pro tip: Clarify whether the API returns direct dependencies only and if the graph is acyclic; mention that you'll cache results to avoid redundant API calls, which is crucial for efficiency in real-world systems.

1. Clarify requirements and constraints

Ask if the API returns direct dependencies only, if the graph is guaranteed acyclic, and what to return on cycle (empty list or error). Confirm if the target package itself should be included in the build order.

2. Model as a graph and choose traversal

Represent packages as nodes and dependencies as directed edges. Decide between DFS with recursion stack for cycle detection or Kahn's algorithm (BFS with in-degree) for topological sorting.

3. Implement topological sort with cycle detection

Traverse the graph starting from the target, recursively fetching dependencies via the API. Use a visited set and a recursion stack (or in-degree counts) to detect cycles and build the order.

4. Handle edge cases and return result

If a cycle is detected, return an empty list or throw an error as specified. Otherwise, return the build order ensuring dependencies appear before dependents.

5. Optimize and discuss trade-offs

Mention caching API results to avoid repeated calls, and discuss time/space complexity (O(V+E)). Consider iterative vs recursive DFS for large graphs to avoid stack overflow.

Key Points to Mention

Topological sorting using DFS or Kahn's algorithm
Cycle detection via recursion stack or in-degree counts
Caching API responses to avoid redundant calls
Handling the target package correctly (include or exclude based on requirements)
Time and space complexity analysis (O(V+E) time, O(V) space)
Edge cases: empty graph, self-dependency, multiple valid orders

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