Hacker News Reader

I would put each element from each set into a Disjoin-set data structure [1] and then report back all the sets whose elements all have cardinality 1.

The complexity of this data structure is pretty interesting. It basically comes to O(N) for N < any number that can be represented in the known universe. It's also the coolest use of the inverse ackermann function I've seen!

How to solve this on a distributed system I have no idea.

[1] https://en.wikipedia.org/wiki/Disjoint-set_data_structure

The standard data structure to look for in this case is the disjoint-set data structure (also called union-find), https://en.wikipedia.org/wiki/Disjoint-set_data_structure. That should make your function fairly easy to implement.

Thanks for that - I'll take a look!

You could model the problem as a graph (each integer represents a vertex and two consecutive integers an edge, e.g. (1, 2, 3) is a graph with nodes 1,2,3 and edges between 1 and 2 and 2 and 3). Then your problem is just to find all connected components of the graph (https://en.wikipedia.org/wiki/Connected_component_(graph_the....

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.

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).

[(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.

Great exercise! Here's my solution in Java, seems be about O(n):

    class Ptr {
        public Ptr next;
    }
    
    <T> List<List<T>> mergeIntersecting(List<List<T>> lists) {
        Map<T, Ptr> lookup = new HashMap<>();
        Map<Ptr, List<T>> output = new HashMap<>();
        for (List<T> list : lists) {
            Ptr ptr = new Ptr();
            if (list.isEmpty()) {
                output.put(ptr, new ArrayList<>());
            }
            for (T value : list) {
                Ptr prev = lookup.get(value);
                lookup.put(value, ptr);
                while (prev != null && prev != ptr) {
                    Ptr tmp = prev.next;
                    prev.next = ptr;
                    prev = tmp;
                }
            }
        }
        for (Map.Entry<T, Ptr> entry : lookup.entrySet()) {
            Ptr ptr = entry.getValue();
            while (ptr.next != null) {
                ptr = ptr.next;
            }
            if (!output.containsKey(ptr)) {
                output.put(ptr, new ArrayList<>());
            }
            output.get(ptr).add(entry.getKey());
        }
        return new ArrayList<>(output.values());
    }

If I give it random lists of integers, it takes around 1 microsecond per element of input. Really curious if there's any way to speed it up a lot.

Robert Sedgewick's course [1] and associated book/booksite [2] have a good overview of Union-Find problem and various algorithms to solve it.

[1] https://www.coursera.org/learn/algorithms-part1

[2] http://algs4.cs.princeton.edu/15uf/

Indeed, Union-Find is the first subject the course covers, because it uses it as an example of an elementary algorithm.

You could just go on merging sets with each other.

For i from 0 to n-1 , find all sets from i+1 to n-1 which have a non empty intersection with set i. Union set i with all those sets and replace i with the union set.

If you use a disjoint set data structure this will be quadratic or O(n^2)

EDIT: On further thought you need to merge from the end and backwards.

This is wrong headed.

Just add everything one by one to a Disjoint set union.

My bad.

I had a similar interview question at Booking.com once. You can solve it in linear time with some extra space (worst case - linear) for two constant-time lookup structures.

Your two examples have the same inputs but different outputs if I am reading this right. What did I miss?

The second example provides one more input set (8,10). So the first example has only 3 sets as input, the second example has 4 sets.

On mobile, the 4th set is hidden until the line is dragged left.

Dang my bad. Thanks for clarifying.

Here's a shell script for the case where the sets are too big to fit in memory, assuming that you are on a Unix system and it has a sort program that can sort a file that won't fit in memory.

Input: one file per set, with names of the form set.X. Format of the file is one value per line. E.g., the set (1, 2, 3) might be in file set.0 with contents

  1
  2
  3

Output: each run of the script will merge overlapping set.X files, deleting files that are made redundant. It will tell you how many sets were merged.

Run the script repeatedly until it says "merged 0".

    #!/bin/bash
    for i in set.*
    do
        sed -e "s/$/ $i/" < $i
    done | sort -k 1 -n > m.$$
    last_val=-1
    last_set=
    merged=0
    while read in
    do
        set x $in
        if [ $2 -eq $last_val ]
        then
            if [ -f $3 ]
            then
                cat $last_set $3 | sort -n | uniq > t
                mv t $last_set
                rm $3
                merged=$((merged + 1))
            fi
        else
            last_val=$2
            last_set=$3
        fi
    done < m.$$
    rm m.$$
    echo merged $merged

The above does more passes over the complete set of elements than is necessary, in order to minimize memory use. At the cost of a little more memory, it could write the commands done in the while loop (cat|sort|uniq;mv;rm) out to a file, and then edit that file to adjust it to take into account the affect of the rm's, and then do one pass of merging.

That would look something like this. First, you'd run this script once:

    #!/bin/bash
    for i in set.*; do sed -e "s/$/ $i/" < $i; done | sort -k 1 -n > m
    last_val=-1
    last_set=
    line=2
    > s
    while read in
    do
        set x $in
        if [ $2 -eq $last_val ]
        then
            #echo "if [ -f $3 ]; then cat $last_set $3 | sort -n | uniq > t; mv t $last_set; rm $3; fi"
            echo "cat $last_set $3 | sort -n | uniq > t; mv t $last_set; rm $3"
            echo "$line,\$s/$3/$last_set/g" >> s
            line=$((line + 1))
        else
            last_val=$2
            last_set=$3
        fi
    done < m > c

That gives an output command file, c, that looks like this:

  cat set.4 set.7 | sort -n | uniq > t; mv t set.4; rm set.7
  cat set.0 set.5 | sort -n | uniq > t; mv t set.0; rm set.5
  cat set.1 set.5 | sort -n | uniq > t; mv t set.1; rm set.5
  cat set.5 set.7 | sort -n | uniq > t; mv t set.5; rm set.7
  cat set.2 set.6 | sort -n | uniq > t; mv t set.2; rm set.6
  cat set.3 set.6 | sort -n | uniq > t; mv t set.3; rm set.6

Note the problem with this. Line #1 removes set.7 after merging it with set.4. But line #4 refers to set.7. Since 7 was merged into 4, it needs to refer to set.4 at that point, not set.7.

The script that made c also outputs a file, s, with sed commands to do the above fix. For the above example, it looks like this:

  2,$s/set.7/set.4/g
  3,$s/set.5/set.0/g
  4,$s/set.5/set.1/g
  5,$s/set.7/set.5/g
  6,$s/set.6/set.2/g
  7,$s/set.6/set.3/g

There is still a problem, because note that s suffers from the same problem that c does! Line #4 of s also refers to set.7, but at that point it should be set.4.

So, before using s to fix s, we have to use s to fix s: "sed -f s < s > s2", giving this for s2:

  2,$s/set.7/set.4/g
  3,$s/set.5/set.0/g
  4,$s/set.0/set.1/g
  5,$s/set.4/set.0/g
  6,$s/set.6/set.2/g
  7,$s/set.2/set.3/g

In this case, that is sufficient. We could now "sed -f s2 < c > c2" and then "bash c2", and we'd be left with set.1 and set.3, with the other sets properly merged in.

However, in more complicated cases one application of s to itself is not always enough. What we really should do is keep applying it to itself until we hit a fixed point, so "sed -f s2 < s2 > s3" giving:

  2,$s/set.7/set.4/g
  3,$s/set.5/set.0/g
  4,$s/set.0/set.1/g
  5,$s/set.4/set.1/g
  6,$s/set.6/set.2/g
  7,$s/set.2/set.3/g

and if you them apply s3 to itself, you will see that there is no change, so s3 is our fixed point. We could then "sed -f s3 < c > c3". Turns out that c3 is identical to c2, so we get the same results as earlier.

Assuming everything fits in memory, the following seems reasonable. The basic idea is to essentially think of each set as a region in some abstract space. If two sets have an element in common, then they are directly connected in that space. Build a map of these direct connections, and then you can use a flood fill to find connected regions. Each connected region corresponds to an output set.

Here's a test implementation, assuming input is one line per input set with space separated values on each line. Output format is the same.

    #!/usr/bin/env perl
    use strict;

    my @in;
    my @out;
    my %sawin;
    my %merge;
    my %merged;

    while (<>)
    {
        chomp;
        s/^\s+//;
        push @in, [split /\s+/];
    }

    for (my $i = 0; $i < @in; ++$i) {
        foreach (@{$in[$i]}) {
            if (defined $sawin{$_}) {
                $merge{$i}{$sawin{$_}} = 1;
                $merge{$sawin{$_}}{$i} = 1;
            } else {
                $sawin{$_} = $i;
            }
        }
    }

    foreach (my $i = 0; $i < @in; ++$i) {
        my %out;
        next if $merged{$i};
        $merged{$i} = 1;
        $out{$_} = 1 foreach @{$in[$i]};
        foreach my $ms (expand_merge($i)) {
            $merged{$ms} = 1;
            $out{$_} = 1 foreach @{$in[$ms]};
        }
        push @out, [sort {$a<=>$b} keys %out];
    }

    foreach (@out) {
        print join(" ", @$_), "\n";
    }

    sub expand_merge
    {
        my($base) = @_;
        my @todo = keys %{$merge{$base}};
        my %done = ($base => 1);
        while (@todo) {
            my $next = shift @todo;
            next if $done{$next};
            $done{$next} = 1;
            push @todo, keys %{$merge{$next}};
        }
        return keys %done;
    }

Everything should be linear in the total number of elements except for expand_merge (the flood fill-like part). I think worst case for expand_merge could be quadratic in the number of elements, which would occur if each set overlapped a large fraction of the other sets.

If things won't fit in memory, I don't know how to do it in the general case. I suppose the first thing I'd do is look at the source of the sets to see if there are any limits on that. For instance, if we are dealing with a very large number of sets without a lot of members per set, and the range of numbers in each set is not very large, then it should be possible to partition the input into two sets of sets, A and B, such that it is easy to show that no sets in A contain any overlap with any sets in B, so we've reduced the problem to two smaller problems that can be solved independently and their outputs concatenated. Repeat.

For the general case, I'd start out by sorting the elements of each set, and by sorting the set of sets. While Googling for a refresher on external sorting and then coding up that part, I'd be hoping for some flash of brilliance to deal with what to do after that.

If no flash of brilliance arrived, I'd probably try something like this (assuming that I can at least fit several of the sets into memory at once). Let's assume that each set is stored in a file, named after its order in the sorted list of sets.

Read the first set into memory. Then scan through the remaining sets, in sorted order, checking each for overlap with the first. For any that overlap, merge them in memory with the first. When all the sets have been processed, or a point is reached where the first element of the current set is larger than the last element of the merged first set and so you can infer that no more merging will happen on this pass, write the merged first set out, replacing the original first set, and delete the files for all the sets that merged with the first.

Repeat this until no new sets merge with the first. At this point, you can mark the first as done, and it becomes the first output set.

Repeat with the first remaining set as your new first set, and so on.

As long as the biggest single output set and the biggest single input set will both fit in memory at the same time, I think that the above approach works.

I have a feeling that there is some clever way to do this that is much more efficient and is much more obvious (in the mathematical sense...in other words, after you look at it for a very long time and think about it really really hard it was clearly obvious).

My guess is that the clever solution will heavily involve sorting...not that I'm really going out on a limb with that guess, because almost everything is sorting when you look at it right. For example, here's a shell script that given a list of x, y coordinates on STDIN (one coordinate pair per line, x and y separated by space) outputs the result of doing one generation of Conway's Life with the input being the initial cell configuration:

    > alive.$$
    while read cells
    do
        echo $cells >> alive.$$
        set x $cells
        x=$2
        y=$3
        echo $x $((y-1))
        echo $x $((y+1))
        echo $((x-1)) $((y-1))
        echo $((x-1)) $y
        echo $((x-1)) $((y+1))
        echo $((x+1)) $((y-1))
        echo $((x+1)) $y
        echo $((x+1)) $((y+1))
    done | sort | uniq -c > neighbors.$$
    grep '^ *3' < neighbors.$$ | sed -e 's/^ *[0-9].//'
    grep '^ *2' < neighbors.$$ | sed -e 's/^ *[0-9].//' > has2.$$
    sort alive.$$ -o alive.$$
    comm -12 has2.$$ alive.$$
    rm has2.$$ neighbors.$$ alive.$$

Note that the key operation is "sort". This runs in O(n log n) where n is the number of live cells (assuming your Unix uses an n log n sort...).