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

IntermediatePrefer not to say

Jun 2026

Summary

Meta SWE coding round, one algorithm question about graph topology detection. Pretty niche problem, not your usual LeetCode grind.

Questions Asked (1)

Given a graph with N nodes and M edges, determine its network topology. Return 1 if it's a linear chain (Bus), 2 if one node connects to all others (Star), 3 if it forms a cycle (Ring), or -1 if it doesn't match any of those.

Algorithms & Data StructuresSystem Design

Author's notes

Took me a minute to even parse what they were asking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, validate the basic edge count conditions for each topology: Bus requires M = N-1, Ring requires M = N, and Star requires M = N-1. Then, compute the degree of each node and check the degree distribution: Bus has exactly two nodes of degree 1 and all others degree 2; Ring has all nodes degree 2; Star has one node of degree N-1 and all others degree 1. Finally, for Bus and Ring, verify connectivity to rule out disjoint cycles or multiple components.

Pro tip: Always handle edge cases like N=1, N=2, and self-loops or duplicate edges explicitly, and mention that the solution runs in O(N+M) time, which is optimal for this problem.

1. Check basic edge count conditions

Verify if M equals N-1 (possible Bus or Star) or M equals N (possible Ring). If neither, return -1 immediately.

2. Compute degree of each node

Traverse all edges and count the degree of each node. This will help identify the degree distribution pattern.

3. Identify topology from degree distribution

For Star: exactly one node has degree N-1 and all others degree 1. For Bus: exactly two nodes have degree 1 and all others degree 2. For Ring: all nodes have degree 2.

4. Verify connectivity for Bus and Ring

Use BFS/DFS or Union-Find to ensure the graph is connected. For Bus, also ensure no cycles (which is implied by M=N-1 and connectivity). For Ring, ensure it's a single cycle.

5. Handle edge cases and return result

Check for N=1 (single node: could be considered Bus or Ring? clarify with interviewer), N=2 (two nodes with one edge: Bus), and ensure no self-loops or multiple edges. Return the appropriate topology code.

Key Points to Mention

Edge count conditions: Bus and Star have M=N-1, Ring has M=N.
Degree distribution: Bus (two degree-1, rest degree-2), Star (one degree-(N-1), rest degree-1), Ring (all degree-2).
Connectivity check is necessary for Bus and Ring to avoid false positives (e.g., disjoint cycles).
Time complexity O(N+M) and space complexity O(N) using adjacency list or degree array.
Edge cases: N=1, N=2, self-loops, duplicate edges, and disconnected graphs.
Clarify assumptions with interviewer (e.g., whether N=1 is considered a Bus or Ring).

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