← Bytedance Interview Insights

Bytedance·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Bytedance software engineer interview that zeroed in on graph algorithms, specifically topological sort. Pretty standard for this kind of role but they wanted you to know both approaches cold, not just one.

Questions Asked (1)

Q1

Given a directed acyclic graph with n nodes and a set of edges, return a valid topological ordering of the nodes. If the graph has a cycle, return an empty list. Be ready to discuss both BFS-based and DFS-based approaches.

Algorithms & Data Structures
Author's notes

They wanted both solutions, not just one.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then present both Kahn's algorithm (BFS-based) and DFS-based topological sort. Explain the time and space complexity of each, and discuss how to detect cycles. Finally, walk through a small example to illustrate the chosen approach.

Pro tip: Mention that Kahn's algorithm naturally detects cycles by checking if the number of processed nodes equals n, while DFS uses a recursion stack to detect back edges. This shows you understand the trade-offs and can adapt to different scenarios.

1. Clarify requirements and edge cases

Confirm input format, whether nodes are 0-indexed or 1-indexed, and if the graph is guaranteed to be a DAG. Discuss edge cases like empty graph, single node, and disconnected components.

2. Present BFS-based approach (Kahn's algorithm)

Explain computing in-degrees, using a queue to process nodes with zero in-degree, and decrementing in-degrees of neighbors. If the result size is less than n, a cycle exists.

3. Present DFS-based approach

Describe performing DFS with three states (unvisited, visiting, visited) to detect cycles. Add nodes to the result in post-order, then reverse the result to get topological order.

4. Analyze complexity and trade-offs

State that both approaches run in O(V+E) time and O(V+E) space. Discuss that Kahn's is iterative and easier to reason about for cycle detection, while DFS can be more intuitive for some and uses recursion.

5. Walk through an example

Choose a small graph (e.g., 4 nodes with edges 1->2, 1->3, 2->4) and demonstrate the steps of the chosen algorithm, highlighting how cycle detection would work if an edge 4->1 were added.

Key Points to Mention

  • Definition of topological ordering: linear ordering of vertices such that for every directed edge u->v, u comes before v.
  • Kahn's algorithm: uses in-degree and queue; cycle detection by comparing output size to n.
  • DFS-based approach: uses recursion stack and three colors (white, gray, black) for cycle detection; reverse post-order.
  • Time and space complexity: O(V+E) for both approaches.
  • Handling disconnected graphs: both algorithms naturally handle multiple components.
  • Edge cases: empty graph, single node, graph with cycle, graph with multiple valid topological orders.

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