Mid-levelMid (3–6 yrs)CodingPythonMetaAmazonGoogle
Clone Graph
Clone an undirected connected graph. Each node has a value and a list of neighbors. Return the clone of the given node.
Answers use simple, clear English.
Audio N/ATime: O(n + e)Space: O(n)
Quick interview answer
DFS or BFS with a map from original node → clone. Create the clone when first seen, then recursively/iteratively wire neighbor clones from the map.
Detailed answer
DFS or BFS with a map from original node → clone. Create the clone when first seen, then recursively/iteratively wire neighbor clones from the map. Without the map you infinite-loop on cycles.
Full explanation
Without the map you infinite-loop on cycles.
Real example & use case
Duplicating a service-dependency graph before simulating a failure scenario.
Pros & cons
Pros: map breaks cycles cleanly. Cons: O(n) memory for the mapping.
Code example
def clone_graph(node):
if not node:
return None
clones = {}
def dfs(n):
if n in clones:
return clones[n]
copy = Node(n.val)
clones[n] = copy
copy.neighbors = [dfs(x) for x in n.neighbors]
return copy
return dfs(node)Practice code · python (view only · no execution)
def clone_graph(node):
if not node:
return None
clones = {}
def dfs(n):
if n in clones:
return clones[n]
copy = Node(n.val)
clones[n] = copy
copy.neighbors = [dfs(x) for x in n.neighbors]
return copy
return dfs(node)#graph#dfs