The Programming Interview from Hell

If someone asks you the "best" way to do something but does not give you context for the problem being solved then the question is stupid. There is no all-purpose "best" way to do anything when it comes to complex systems. You use the "best" way for the problem in hand that may be shared memory, pipes, writing to a file, RPC, etc.

> I never found out the BEST way to share data between programs

Come on, add another layer of indirection! When given a problem to solve, hand back another problem.

In this case:

Q: "I want the SIMPLEST possible way to synchronize two threads. What is it?"

A: The SIMPLEST possible way to synchronize two threads is a global maximal element (not necessarily unique) of a poset induced by a partial ordering on possible methods for synchronizing two threads. If the induced poset is totally ordered, and assuming that at least one possibly way of synchronizing two threads exists, then there exists a SIMPLEST possible way to synchronize two threads. If you hand me a method for comparing two synchronization methods for SIMPLICITY, then an algorithm retrieving such a best possible solution is trivial, but at this point you must define define what you mean by SIMPLEST before we can move any further.

Mr. Double PhD was trying to be clever.

> I never found out the BEST way to share data between programs. In fact, I'm still looking. I think we all are.

Copy-paste.

"Raise interrupt priority" is not a way to synchronize threads, let alone the simplest. I know what I'm talking about; I worked on multithreading for Linux before the rewrite to NPTL and I invented the PTHREAD_MUTEX_ADAPTIVE_NP type that you still find in Glibc. On a project several years ago, I did use interrupt priority in conjunction with threads as a complete hack. The issue was this: the interrupt service routines for an IDE-based compact flash were running CPU intensive polling loops, taking away app CPU time. I created a priority scheme where certain interrupt priority levels overlapped with thread priority levels. That is, it was possible to suppress the interrupts for this IDE device while certain important threads were dispatched. As in, automatically: when the kernel dispatched a thread in that priority range, interrupts below that value would be blocked (not by disabling CPU interrupts, but the actual interrupt controller's detailed mask of interrupts, where we pick the specific ones that get masked). When the thread lost the CPU, they would be unblocked. This solution/workaround worked well enough to deal with the issue it was intended for.

My guess would be that simplest way to sync two threads is exit them both. ;)

linked list is not complex for christ sake.

If he gave reasonable answers when pressed, despite being initially resistant, it sounds like the interview didn't give any insight into whether he was a good employee or not.

> I'd simply announce that I'm a web developer and not a algorithms person

A while ago I was invited at a startup for a casual discussion about an open position they had (front-end developer). I went because I knew several employees and they were nice. The casual discussion turned out to be several questions about UDP/TCP and writing algorithms on a blackboard (counting leaves in a tree, finding is a word is an anagram, etc.). Nothing really hard, but quite disconnected from the day-to-day job of a front-end developer.

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.

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

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

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.

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.

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

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/

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.

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

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.

I really wish there were more companies like this. Interviewing in SF/Silicon Valley is an absolute nightmare and I've basically given up. I simply can't put myself through that ordeal of weeks of back and forth emailing and talking with recruiters, followed by multiple day long interviews, just to be rejected because I couldn't whip out an algorithm on your white board in front of five people while interviewing for a basic front end position.

Nice. I was once asked to implement a basic filesystem API in C++ including file manipulation, directories and paths, etc. I just said use boost::filesystem and move on with your life. Interviewer was not impressed but at 95% of companies that's what you are going to want to do.

Can you imagine interviewing someone to build you a house and spending 90% of the interview time asking him how he'd chop down trees for wood and manufacture the nails? Welcome to software interviewing.

Of course, you acted like a smartass for no apparent reason.

You will never be asked to reimplement a library function on your job, these questions are used to see how you approach a problem, your reasoning, etc...

Hired.

Seriously that's the correct answer as far as any productive engineer is concerned right?

I've learned in the past few years that, if the interviewers gripe about anything in the interview (especially management), it's best to stay away from that company. In an interview, the company is trying to put it's best face on to sell themselves to you, and if the employees can't hold it in for 30 minutes, that's a bad sign.

I've been on both sides of the horror story style interview -- as an interviewer and an inteeviewee.

As an interviewer, if there was someone we liked, we were brutally honest about the company culture. We (myself and my manager) wanted senior engineers who weren't afraid to speak up and help shake things up in the larger organization. If they still accepted the offer, they were what we wanted. We had too many people quit out of frustration instead of fighting.

At another job I applied to as an architect, the manager told me all of the issues with the processes (and lack there of). He tried to "scare me away". I asked him one question. Will I be able to come in and make the changes needed and will he have my back if I inadvertently step on toes trying to do the right thing? He said yes and I accepted the offer.

I used a polite version of "I'd google it" while interviewing with Google. I explained that I didn't think anyone could be reasonably expected to know how to do everything in every language on demand and that virtually every professional programmer I knew consulted Google from time to time.

Maybe I was just ahead of the times or they weren't looking for someone to be as honest as I was but I didn't make it past round 3 of their interviews.

    new java.util.HashMap()

In case you ever get such a stupid question again.

Modern manhole covers are overwhelmingly round, and cast as not to fall into their own fitting, also cast. Not sure how a obscure counter example does anything other than disprove your point further. Source: worked IT for public civil engineer for a few years.

Heh, I would imagine they just found fellow aristocrats who had seen the puzzle questions before and whose groupthinking conformity was a perfect match for the companies.

I've also called out crappy interviews - while in the interview. I went on to be offered the job - but declined.

that's illegal in many countries america is fucked up

I think everyone should get overtime pay, it would make the company think about how to get better utilisation out of their staff in an allotted time.

We are an equal opportunity employer, we hide behind the market and external factors to discriminate salaries.

Knowing of data structures is more important IMO. The hoops I've seen people jump through in code because they don't know about sets.

Wait, how is a linked list a non-trivial data structure? It just consists of: {data, pointer to next element}.

Not even just system programming. It's a fundamental data structure and concept. I don't think it's unreasonable for a company to say: we expect this role to understand what goes on behind this abstraction.

I once had an interview where they gave me some programming problems, prewritten unit tests that were failing that I had to make pass, a laptop and told me to use any resource I wanted to help and left me in a room for hour. It was one of the best technical interviews I've had.

loooooooooooooooooooool.

Punctuation is your friend.

You should definitely contact a reddit user called CommaHorror.

This is his writing style, which I believe would complement yours quite nicely: https://www.reddit.com/user/commahorror