Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Meta SWE coding round, one question on graph cloning. Pretty focused session, no fluff.

Questions Asked (1)

Given the starting node of an undirected graph where each node holds an integer value and a list of neighbors, write a function that returns a deep copy of the entire graph.

Algorithms & Data Structures

Author's notes

The adjacency list representation tripped me up for a second because you have to track visited nodes or you'll loop forever on cycles.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to track original nodes to their copies, then perform a depth-first search (DFS) or breadth-first search (BFS) from the starting node. For each node, create a copy if it doesn't exist, then recursively (or iteratively) copy all its neighbors and link them to the copy.

Pro tip: Clarify whether the graph can have cycles or duplicate edges, as this affects the need for a visited map. Mention that you'd handle disconnected graphs by iterating over all nodes if the entire graph isn't reachable from the start.

1. Clarify requirements and edge cases

Ask about graph size, cycles, self-loops, and whether the graph is connected. Confirm that a deep copy means new nodes with the same values and neighbor relationships.

2. Choose traversal and data structure

Decide between DFS (recursive or iterative) and BFS. Use a hash map (dictionary) to map original nodes to their copies to avoid infinite loops and duplicate work.

3. Implement the copy logic

Write a function that takes a node, checks if it's already copied, creates a new node if not, and then recursively copies all neighbors and adds them to the new node's neighbor list.

4. Handle disconnected components (if needed)

If the graph may not be fully reachable from the start, iterate over all nodes and apply the copy function to each unvisited node.

5. Test and analyze complexity

Test with simple graphs, cycles, and large graphs. State that time and space complexity are O(N + E) where N is number of nodes and E is number of edges.

Key Points to Mention

Use a hash map to track visited nodes and their copies to handle cycles.
Choose between DFS and BFS; both work, but DFS is simpler recursively.
Ensure deep copy: new nodes with same values and independent neighbor lists.
Time and space complexity: O(N + E) for both, where N is nodes and E is edges.
Edge cases: empty graph, single node, self-loops, disconnected graph.
Avoid modifying the original graph; the copy should be completely independent.

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