← Snap Interview Insights

Snap·Backend Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Snapchat backend round, one algorithmic problem the whole way through. Pretty graph-heavy, which I should've expected but didn't really prep for specifically.

Questions Asked (1)

Q1

You're given a 2D array of edges representing connections between employees. Employees in the same connected component belong to the same group. Return the total number of cross-group pairs you can form by picking one person from each of two distinct groups.

Algorithms & Data Structures
Author's notes

The example they gave was edges like [[0,1],[0,2],[3,4]], which produces groups of size 3 and 2, giving 6 valid pairs.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify all connected components (groups) in the graph using Union-Find or BFS/DFS. Then, compute the total number of cross-group pairs by summing the products of the sizes of every pair of distinct groups, or equivalently (total^2 - sum(size_i^2))/2. This approach runs in O(E α(V)) or O(V+E) time, which is optimal.

Pro tip: Mention that you can avoid double-counting by using the formula (total^2 - sum(size_i^2))/2, and note that this handles large inputs efficiently. Also, clarify that the graph is undirected and may be disconnected.

1. Clarify the problem

Confirm that edges represent undirected connections and that groups are connected components. Ask if the graph can be disconnected or have isolated nodes.

2. Choose a component-finding algorithm

Decide between Union-Find (disjoint set union) or BFS/DFS. Union-Find is efficient for dynamic connectivity, while BFS/DFS is straightforward for static graphs.

3. Compute group sizes

After identifying components, count the number of employees in each group. Store these sizes in a list.

4. Calculate cross-group pairs

Use the formula: total pairs = (total_employees^2 - sum(size_i^2)) / 2. Alternatively, iterate over groups and sum size_i * (total_employees - size_i) / 2 to avoid double-counting.

5. Analyze complexity and edge cases

State time and space complexity. Discuss edge cases: no edges (all isolated), fully connected graph, and large number of nodes.

Key Points to Mention

  • Connected components in an undirected graph
  • Union-Find (Disjoint Set Union) with path compression and union by rank
  • BFS/DFS for component traversal
  • Formula for cross-group pairs: (total^2 - sum(size_i^2))/2
  • Time complexity: O(E α(V)) for Union-Find or O(V+E) for BFS/DFS
  • Handling disconnected graphs and isolated nodes

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