← Bytedance Interview Insights

Bytedance·Software Engineer·Technical Phone Screen·Senior

Senior
Jun 2026

Summary

Bytedance SRE interview with a graph traversal problem that looks straightforward until you miss the asymmetry detail and your whole approach falls apart.

Questions Asked (1)

Q1

You have n bombs, each with a position and explosion radius. Detonating one bomb triggers any other bomb whose center falls within that radius, and those bombs trigger their own, chain-reaction style. Find the starting bomb that causes the maximum total detonations.

Algorithms & Data Structures
Author's notes

My first instinct was to just check all pairs and do some kind of flood fill, which is basically right, but I initially modeled it as an undirected graph and that was wrong.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the bombs as a directed graph where an edge exists from bomb A to bomb B if B's center lies within A's blast radius. For each bomb, compute the size of its reachable set (e.g., via BFS/DFS or SCC condensation) and return the bomb with the maximum reachable count.

Pro tip: Mention that you can optimize by precomputing reachability with bitsets or by using SCC condensation to handle cycles, and always clarify edge cases like duplicate positions or zero radius.

1. Clarify and define the problem

Confirm that detonation is directional (A triggers B if B is within A's radius) and that chain reactions follow directed edges. Ask about constraints (n, coordinate ranges) to guide algorithm choice.

2. Build the graph

For each pair of bombs, check if the distance between centers is ≤ the source bomb's radius. This yields a directed graph; for large n, consider spatial indexing to avoid O(n²) checks.

3. Compute reachability

For each node, run BFS/DFS to count reachable nodes. Alternatively, find strongly connected components (SCCs) and condense the graph to a DAG, then compute reachable set sizes via DP/topological order.

4. Find the maximum

Track the bomb that yields the largest reachable count. If multiple, return any (or the smallest index, depending on problem statement).

5. Analyze complexity and optimize

Discuss time/space complexity. For dense graphs, bitset-based reachability can be efficient. Mention trade-offs between BFS per node and SCC-based approach.

Key Points to Mention

  • Graph modeling: directed edge from bomb i to bomb j if distance(i,j) ≤ radius[i].
  • Reachability computation: BFS/DFS from each node or SCC condensation to handle cycles.
  • Complexity: O(n²) graph construction; O(n(n+m)) for BFS per node; SCC approach can be O(n+m) for condensation plus DP.
  • Optimization: bitset reachability for dense graphs, spatial indexing (e.g., k-d tree) for large n.
  • Edge cases: duplicate positions, zero radius, self-loops, disconnected components.
  • Correctness: prove that reachable set in graph equals total detonations.

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