Amazon | Phone Screen | Merge duplicate graph nodes
Anonymous User
655

Given a list of graph edges:
a->b, a->c, b->d, c->d

Merge all nodes that have share all the same edges going in and share all the same edges going out. So in the above example, we should merge b and c into the node bc because they both share a as an in-edge and share d as an out-edge.

Output should be like:
a->bc, bc->d

Another example:
a->b, a->c, b->d, c->d, b->e, c->e
returns
a->bc, bc->de

So first I put everything into an adjacency list. Then I reversed the edges and created an adjacency list out of that to create a graph of in-edges. Then for each node in the graph, I check its in-edges and the out-edges against the in-edges and out-edges of every other node, and merge into a new node if they are equal.

However, this is n^2 run time, and I only managed to merge bc->d but not a->bc.

I feel that went poorly. How would I do this?

Comments (6)