The Programming Interview from Hell
OK - but here&#x27;s a genuine problem that came up the other day in my work (reconciling two datasets - we have various many-to-one mappings of ids that we then want to reconcile against each other). I think it&#x27;s quite a neat computer science&#x2F;algorithm challenge, so here goes:<p>Write a function which takes as input a list of sets, many of which are not disjoint, but will output a list of sets where all of the non-disjoint ones have been merged back together again. So the output is a list of sets which are all disjoint from each other because any intersecting sets have been merged together.<p>e.g. given the input:<p><pre><code>    [(1,2,3), (2,4,8), (10,11,12)]
</code></pre>
it will report back:<p><pre><code>    [(1,2,3,4,8), (10,11,12)]</code></pre>
because (1,2,3) and (2,4,8) are not disjoint, but the (10,11,12) set is.<p>Whereas given the input:<p><pre><code>    [(1,2,3), (2,4,8), (10,11,12), (8,10)]
</code></pre>
it would report back a single set:<p><pre><code>    [(1,2,3,4,8,10,11,12)]
</code></pre>
because now all of the sets are connected - the 8 and the 10 now connect everything else together.<p>I came up with an algorithm which is acceptable for the dataset we currently have - but I&#x27;ve no idea what time complexity it is (for our real dataset it was able to do it in &quot;one pass&quot; - but in principal it could be worse than that). I don&#x27;t know how I would implement a distributed version if the list of sets was too big to fit in memory, etc. etc.<p>And I haven&#x27;t found a good solution on Google (but I&#x27;m not even sure <i>what</i> to Google).