An interesting list structure, part 3

This is the story of how I was no-hired by Microsoft; surprisingly, it is germane to our discussion of unusual list structures.

I was a Waterloo co-op intern three times at Microsoft, each time working for the Visual Basic team; that's where I learned how industrial developer tools work, how to build a localizable product, and many other valuable lessons. The VB team told me that on the strength of my internships - which, after all, was in total a 12 month long interview spread over two years - that they'd give me a job when I graduated. However, the VB managers were both smart and kind, and encouraged me to look around the company more broadly to see if there was any other team that I might be a good fit for.

I ended up interviewing with two or maybe three other teams; this was over 20 years ago and my memory is a bit hazy. A few points do stand out though. I had an interview with the ill-fated Blackbird team that I thought went pretty well - the technical question was about rapidly finding the seven letter words in a Scrabble rack, and I gave the standard solution of preprocessing the dictionary into a multi-dictionary that answers the question in O(1) time, and then discussed how to use a trie to solve the more general problem. I'm not sure why they no-hired me, but that team was about to be disbanded so I dodged a bullet there. In retrospect, this was over a year after the "tidal wave email" and I am surprised they lasted as long as they did.

But the thing that really stands out is my interview with the SQL Server team. The day I interviewed there was a snowstorm in the greater Seattle area, which is quite rare and there is not infrastructure to rapidly clear the streets. A grand total of zero of the people scheduled to interview me came into work that day, and so recruiting had to scramble to find interviewers. The technical question I got from the SQL team was "reverse a linked list in C++" - that was the extent of the problem statement, so I asked "Can I assume I already have a linked list class defined?" Sure. "Is it acceptable if the original list is destroyed?" Sure. "OK," I said, and wrote on the whiteboard something like:

LinkedList reverse(LinkedList list) { LinkedList result; while (!list->is_empty()) result.push(list.pop()); return result;}

I'm probably missing some syntactic details there; I haven't programmed in C++ in fifteen years. But you get the idea; reversing a linked list is logically just popping the old list and pushing onto the new list.

The interviewer just said something like "that's wrong", and I said "no, that's right but would you like me to implement push and pop to show you how they work?" and it went downhill from there.

That was super confusing to me at the time. I realized much later - like, years later, when I started doing interviews myself - that the interviewer was unprepared, was not expecting to do an interview that day, may have been a very inexperienced interviewer, probably picked a problem at random, and worst of all had a specific "correct" solution in mind. Almost certainly the "correct" solution was the solution where you traverse the list and rejigger the "next" pointer "in place" as you go, which of course is how you reverse a linked list in C. (I am often surprised at the number of people in interviews who write C-style solutions in C++ or C#, as though those languages did not have a culture of encapsulation of implementation details.)

So it was a confusing day and a bunch of no-hires, but no harm done. Obviously I ended up having a successful 16 year stint at Microsoft regardless, and I learned from example how not to conduct a technical interview.

All this was on my mind as I was writing this series because the original paper by Hughes that introduced the concept I've been discussing is called A novel representation of lists and its application to the function "reverse".

What on Earth does "reverse a linked list" have to do with this unusual representation of linked lists? I won't go through the whole argument presented in the Hughes paper because it gets a bit technical, but I'll give you what was for me the key insight.

Suppose we have our "simple" linked list from last time, where a list is either empty, or a head value and a tail list. How do you reverse that linked list? The problem here is posed in the context of functional languages where we do not have mutable local variables and loops, so a recursive solution is required.

If we have an "append" operation available then the naive recursive way to reverse a simple list is to say "recursively reverse the tail, and then append the old head to the reversed tail". That is, if we have 1, 2, 3, then we recursively reverse 2, 3 into 3, 2, and then append 1 to get 3, 2, 1. In our implementation that would be:

public SimpleList<T> NaiveReverse() =>
this.IsEmpty ?
this :
this.Pop.NaiveReverse().Append(this.Peek);

The problem with that should be clear given our previous discussion. We recurse once per list element, so we recurse O(n) times. But Append is an O(n) operation on simple lists, so the total complexity is O(n²), which is pretty bad.

The standard O(n) solution is to emulate my little loop above, but non-destructively and recursively:

private SimpleList<T> ReverseWithTail(SimpleList<T> tail) =>
this.IsEmpty ?
tail :
this.Pop.ReverseWithTail(tail.Push(this.Peek));
public SimpleList<T> Reverse() => this.ReverseWithTail(Empty);

But" hold on a minute here. If we said

Func<SimpleList<T>, SimpleList<T>> f = someList.ReverseWithTail;

Then what we've got is an object that represents a list - in this case, it represents the list that is someList reversed - where the object is a function such that when you give it a list, it gives you back the represented list concatenated with the given list, in O(n) time; a delegate to ReverseWithTail is exactly the data stored in a Hughes list!

So perhaps it is not that bizarre to represent a list as a concatenation function. Functional programs are chock-full of algorithms like this one, where the "tail end" of a list is being passed in and the algorithm represents the operation of stuffing values onto the left side of it. The genius of the Hughes list is to recognize that this technique can be generalized into an elegant, useful data type that defers expensive work until it is needed.

Next time on FAIC: System.Random is the source of so many bugs; could we come up with a better design? This is going to be a long series, because there's a lot of improvements we could make. We're not yet programming at the correct level of abstraction when it comes to dealing with randomness; let's see how we can fix that.