Clone Graph

Python data engineering interview problem. Difficulty: advanced. Pattern: Graphs. About 18 minutes. Part of the Pro drill bank.

Deep-copy an undirected graph given as an adjacency dict. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A graph may be shared by several consumers, so copying only its outer dictionary can make one consumer's changes affect the original graph. Return a deep copy of the adjacency dictionary. Preserve every node and neighbour, and sort each copied neighbour list in ascending order. Write clone_graph(adj: dict) -> dict. The 4-node sample keeps neighbours [2, 4], [1, 3], [2, 4] and [1, 3] in sorted order. The starter file already has the function name and harness print lines. Keep them and fill only the function body.

Requirements

• Create independent neighbour lists.
• Preserve every node label and edge.
• Sort each neighbour list before returning.

Constraints

• Keys are node labels and values are neighbour lists.
• The return type is a dictionary with list values.

Examples

Input: clone_graph({1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}) Output: {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]} Deep copy preserves edges.

Topics: lakebench, python, clone, dfs.

More Python interview questions · All interview problems · Learn data engineering