I did a cool thing at work

There’s a somewhat-famous programming interview problem.  I think they use it at Google.  It goes like this:

You have a pointer to the first element of a singly linked list.  Your job is to determine whether there’s a cycle in the list in linear time and constant memory.  I remember my thought process, and I don’t mind telling you that I didn’t solve the problem unassisted.  But I love problems, so I remember it.  Sorry if the pseudocode is hard to read.  I tried describing the code in prose and it was even worse. I also apologize if the formatting is bad; I’m not so hot with html, so there’s probably a better way to get tabs in the code than using   four times.

Here’s the naive solution:

def listContainsCycle(firstElement):
    iterator = firstElement;
    while(True):
        if(iterator.hasNoSuccessor()):
            return False;
        iterator = iterator.getSuccessor();
        if(iterator == firstElement):
            return True;

This fails when, say, the fourth element’s successor is the second element.  Then you’ll loop forever as your iterator goes first, second, third, fourth, second, third fourth…  until you think of the not-so-naive solution:

def listContainsCycle(firstElement):
    allElements = empty array;
    allElements.append(firstElement);
    while(True):
        lastElement = allElements.getLastElement();
        if(lastElement.hasNoSuccessor()):
            return False;
        nextElement = lastElement.getSuccessor()
        if(allElements.contains(nextElement)):
            return True;
        allElements.append(nextElement);

This will detect whether or not there’s a cycle, but it doesn’t use constant space.  By the end, you’ll have the whole list in memory.  Here’s the solution that uses constant space:

def listContainsCycle(firstElement):
    slowIterator = firstElement;
    fastIterator = firstElement;
    while(True):
        if(fastIterator.hasNoSuccessor()):
            return False;
        fastIterator = fastIterator.getSuccessor();
        if(fastIterator.hasNoSuccessor()):
            return False;
        fastIterator = fastIterator.getSuccessor();
        slowIterator = slowIterator.getSuccessor();
        if(fastIterator==slowIterator):
            return True;

The way this works is by having two iterators, one of which goes twice as fast as the other. If there’s a cycle, the fast iterator will eventually “lap” the slow one, and they’ll be pointing at the same thing again.

Here’s where the cool thing is! Well, if you don’t think the above code problem is cool. Well, to be honest, if you didn’t think that was cool, you probably won’t think this is cool. But I do, so I do. The cool thing is, I got to implement this for real, at work! At IMVU, people can create virtual products. Each product has to be derived from a parent product, like a class inheriting from another class. There are some special products authored by IMVU inc that don’t have parent products, and all other products have to derive from products that derive from products that eventually derive from IMVU base products.

Every time someone buys a product, their money is used to pay everyone who authored one of the products up the chain, eventually terminating with us. Here’s the thing: if it were somehow possible for a cycle to exist in a product’s derivation chain, then our production code would go into an infinite loop every time someone tried to buy it. When I saw that we needed an algorithm for detecting and preventing these was needed, I used an adaptation of the above algorithm, and it made me happy.

Maybe it’s lame to tack a conclusion onto this, but it pays to love puzzles like this one. You never know when they’ll be helpful. When I interviewed for this job, two of the interview questions were problems I’d seen before. I was up front about this, and I think being the kind of person who loves logic puzzles enough to memorize them was something that helped get me hired.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: