Number of Changed Nodes - Count Graph Nodes That Changed State Between Snapshots

Question

## Round 1 - Coding

## Problem

You are given two snapshots of a directed graph (as adjacency lists). Each node has a value. Between snapshots, some nodes changed their value or their outgoing edges changed. Return the count of nodes that are different in any way between the two snapshots.

```python
def count_changed_nodes(
    snapshot_a: dict[int, dict],  # {node_id: {"value": int, "neighbors": list[int]}}
    snapshot_b: dict[int, dict]
) -> int:
    # Count nodes where value OR neighbor list differs between snapshots
    # Also count nodes that exist in one snapshot but not the other
    ...
```

```
Example:
A = {
    1: {"value": 10, "neighbors": [2, 3]},
    2: {"value": 20, "neighbors": []},
    3: {"value": 30, "neighbors": [1]},
}
B = {
    1: {"value": 10, "neighbors": [2]},   # neighbor 3 removed -> changed
    2: {"value": 99, "neighbors": []},     # value changed
    4: {"value": 40, "neighbors": []},     # new node -> changed
}
# Node 1: neighbor changed
# Node 2: value changed
# Node 3: removed (in A not B) -> changed
# Node 4: added (in B not A) -> changed
count_changed_nodes(A, B) -> 4
```

## Follow-ups

1. How do you compare neighbor lists regardless of order?
2. How would you return a diff (added, removed, modified) rather than just a count?
3. How would you extend this to detect cycles introduced or removed between snapshots?
4. In a distributed system, how would you compute this diff for a graph with 100M nodes?

Number of Changed Nodes - Count Graph Nodes That Changed State Between Snapshots

Question Details

Full Details

Topics

More from DoorDash