Clone a Graph

medium · graph traversal

graph maps string IDs to lists of neighbor IDs; all listed neighbors exist. It may contain cycles, self-loops, repeated neighbors, or disconnected components. Return a deep independent adjacency dictionary for only the nodes reachable from start. Preserve each node's exact neighbor-list order and duplicates; dictionary key order is irrelevant. Return {} if start is None or absent. Build new neighbor lists rather than returning aliases into graph. For this JSON-based exercise, a clone is represented by its reachable adjacency lists, not custom node objects. Examples (JSON; null means Python None): Input: {"graph": {"a": ["b"], "b": ["a"], "c": []}, "start": "a"} Output: {"a": ["b"], "b": ["a"]} Input: {"graph": {"a": ["a", "a"]}, "start": "a"} Output: {"a": ["a", "a"]}

Starter code

def clone_graph(graph: dict[str, list[str]], start: str | None) -> dict[str, list[str]]:
    """Copy the reachable graph while preserving edges and neighbor order."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. InterviewerCharacter joke · No posting date

    Great approach. Now solve it without using the thing you just used.

  2. AntyCharacter joke · No posting date

    This problem has 8 hidden tests. I found 9 ways to fail them.

  3. The GraderCharacter joke · No posting date

    Edge case? Never met her.