The Programming Interview from Hell

Re:The Programming Interview from Hell by Patient0 on Monday February 20, 2017 @09:56AM (#13687736)

Yeah but realising that two "nodes" of the graph are connected requires doing a set intersection, which I concluded was quite expensive to do between all possible sets. i.e. building the "graph" was an expensive operation... unless I've misunderstood you.

[ Parent | on HN ]

Re:The Programming Interview from Hell by s_tim on Monday February 20, 2017 @10:23AM (#13687980)

You build from the different tuples in your list just one graph. Then it's just a simple DFS/BFS with one random start node. Which gives you your first component. Then you can get the second if you start at a node which is not in the previous component until you visited all nodes. This should all be in O(n).

[ Parent | on HN ]

Re:The Programming Interview from Hell by gk101 on Monday February 20, 2017 @10:26AM (#13688024)

[(1, 2, 3), (2, 4, 5)] would result in a graph like this:

1 - 2 - 3

     \

      4 - 5

Building the (undirected) graph would take linear time, and once it is built, you can do a simple Depth First Search to mark all the connected components.

[ Parent | on HN ]