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

Intermediate

Jun 2026

Summary

Google SWE interview with a graph/topological sort problem that had a twist I didn't fully anticipate going in. The deterministic ordering requirement is what separates this from a standard topo sort, and that detail matters a lot.

Questions Asked (1)

Given n tasks labeled 0 to n-1 and a list of dependency pairs where [a, b] means a must complete before b, return the order in which all tasks should be executed such that dependencies are respected. When multiple tasks are ready to run at the same time, always pick the one with the smallest label. Return an empty list if a cycle exists.

Algorithms & Data Structures

Author's notes

I jumped straight to Kahn's algorithm and felt good about it, but then they asked why my output differed from theirs on the example and I realized I was using a regular queue instead of a min-heap.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tasks and dependencies as a directed graph and use Kahn's algorithm for topological sorting. To ensure the smallest label is picked when multiple tasks are ready, use a min-heap (priority queue) to select the next task. If the number of processed tasks is less than n, a cycle exists, so return an empty list.

Pro tip: Mention that using a min-heap instead of a regular queue ensures the lexicographically smallest topological order, which is a common follow-up requirement. Also, discuss how you would handle large inputs by using efficient data structures and avoiding recursion to prevent stack overflow.

1. Understand the problem and clarify constraints

Restate the problem to ensure you understand the dependency representation and the tie-breaking rule. Ask about input size, whether dependencies are given as pairs, and if the graph is guaranteed to be a DAG.

2. Build the graph and compute in-degrees

Create an adjacency list for the graph and an array to track in-degrees of each task. For each dependency [a, b], add b to a's adjacency list and increment b's in-degree.

3. Initialize a min-heap with tasks having zero in-degree

Scan the in-degree array and push all tasks with in-degree 0 into a min-heap (priority queue) to always extract the smallest label first.

4. Process tasks using Kahn's algorithm

While the heap is not empty, pop the smallest task, add it to the result order, and for each neighbor, decrement its in-degree. If a neighbor's in-degree becomes 0, push it into the heap.

5. Check for cycles and return result

After processing, if the result order contains all n tasks, return it; otherwise, a cycle exists, so return an empty list.

Key Points to Mention

Topological sorting using Kahn's algorithm (BFS-based) or DFS-based approach.
Use of a min-heap (priority queue) to ensure smallest label is chosen when multiple tasks are ready.
Time complexity: O(V + E log V) due to heap operations, where V is number of tasks and E is number of dependencies.
Space complexity: O(V + E) for storing the graph, in-degrees, heap, and result.
Cycle detection: if the result list size is less than n, a cycle exists.
Handling edge cases: empty input, no dependencies, multiple valid orders, and disconnected components.

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