The Programming Interview from Hell

P.S : this is replied from desktop. hope this works for you

The technical questions were my fault because I told the interviewer I was a researcher in number theory and enjoyed working with embedded systems.. to which they said, 'oh, can you talk a bit about that?'

Each comma denotes an email response explaining I was chosen to move on and to please fulfill the next request: Send resume with cover letter, fill out online application, make 90s video about why you should serve coffee, first video chat interview, come in to meet recruiter, come in to meet store manager.

I only made it through the first of the three interviews. Ultimately I think we both dodged a bullet there.

Honestly!

Ask an employee next time you get a coffee there what kind of interview process they had to go through.

PS- should have made a 90s '90s video about why I should serve coffee.. definitely would have gotten their minimum wage offering then.

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 $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;
    }

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'  has2.$$
    sort alive.$$ -o alive.$$
    comm -12 has2.$$ alive.$$
    rm has2.$$ neighbors.$$ alive.$$