Bytedance·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Bytedance SRE interview with a graph reachability problem that looked deceptively simple. The complexity analysis at the end is what they actually care about.

Questions Asked (1)

You have n devices, each with a position (x, y) and a range r. Device i can activate device j if the Euclidean distance between them is at most r_i, but not necessarily the other way around. If you manually activate one device, all devices reachable from it directly or through a chain also activate. Which starting device maximizes the total number of activated devices? Also walk through the time and space complexity of your solution.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is a directed graph problem disguised as a geometry question.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the devices as a directed graph where an edge from i to j exists if device i can activate device j. The problem reduces to finding the node with the largest reachable set in this directed graph. Compute the size of the reachable set for each node using BFS/DFS, and return the node with the maximum size.

Pro tip: Mention that the graph can be dense (O(n^2) edges), so building the full adjacency list may be memory-heavy; consider on-the-fly neighbor generation during BFS/DFS to save space, and discuss trade-offs.

1. Model as a directed graph

Treat each device as a node. For every ordered pair (i, j), add a directed edge i -> j if the Euclidean distance between them is <= r_i. This captures the asymmetric activation condition.

2. Compute reachable set for each node

For each node, perform a BFS or DFS to find all nodes reachable from it. Keep track of the maximum reachable count and the corresponding starting node.

3. Optimize with memoization or SCCs

If the graph is large, use memoization to avoid recomputing reachable sets for nodes already visited, or compute strongly connected components (SCCs) and condense the graph to a DAG, then use DP to find the maximum reachable set size.

4. Analyze time and space complexity

Naive BFS/DFS from each node: O(n * (n + m)) time, where m is the number of edges (up to O(n^2)). Space: O(n + m) for adjacency list. With SCC condensation: O(n + m) time for SCC, then O(n + m) for DP on DAG, but building the graph still O(n^2) in worst case.

5. Discuss trade-offs and edge cases

Consider dense vs sparse graphs, memory limits, and whether to build the graph explicitly or generate neighbors on the fly. Handle cases where multiple devices yield the same maximum count (return any).

Key Points to Mention

Directed graph representation and asymmetric edges based on range.
BFS/DFS for reachability from each node.
Time complexity: O(n^3) naive, O(n^2) with optimizations like SCC condensation.
Space complexity: O(n^2) for adjacency matrix or O(n + m) for adjacency list.
Optimization techniques: memoization, SCC condensation, on-the-fly neighbor generation.
Trade-offs between precomputing edges and computing distances on demand.

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