Exercise 22: Suffix Arrays

I'd like to tell you a story about suffix arrays. I was interviewing at a company in Seattle during a time I was curious about how to most efficiently create a diff on an executable binary. My research brought me to the algorithms Suffix Array and Suffix Tree. The Suffix Array is simply where you sort all the suffixes of a string into a sorted list. The Suffix Tree is similar but done more like a BSTree than a list. These algorithms were fairly simple and had fast performance once you did the sorting operation. The problem they solved was finding the longest common substring between two strings (or in this case, lists of bytes).

You can make a suffix array in Python really easily:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

>>> magic = "abracadabra"
>>> magic_sa = []
>>> for i in range(0, len(magic)):
...     magic_sa.append(magic[i:])
...
>>> magic_sa
['abracadabra', 'bracadabra', 'racadabra', 'acadabra',
 'cadabra', 'adabra', 'dabra', 'abra', 'bra', 'ra', 'a']
>>> magic_sa = sorted(magic_sa)
>>> magic_sa
['a', 'abra', 'abracadabra', 'acadabra', 'adabra', 'bra',
 'bracadabra', 'cadabra', 'dabra', 'ra', 'racadabra']
>>>

As you can see, I simply took the suffixes of the string in order, and then sorted the list. But, what does this do for me? Once I have this list, then I can find any suffix I want by simply doing a binary search on this list. This example is very crude, but in real code you can do this very quickly, and you can keep track of all the original indexes so you can then reference the suffixes' original locations. It is very fast compared to other search algorithms and very useful in things like DNA analysis.

Back to the interview in Seattle. I'm in this cold room being interviewed by C++ programmers for a Java job. As you can tell this isn't a very fun interview, and I definitely don't think I'll get the job. I hadn't written any C++ in many years and the job was for Java, of which I was an expert at the time. In walks the next interviewer and he asks me, "How would you find a substring in a string."

Great! I've been studying the hell out of this problem in my free time. I'll nail it! I jump up and walk up to the whiteboard and explain to the guy how to make a suffix tree, how it improves search performance, how a modified heap sort makes it faster, how a suffix tree works, why it's better than a ternary search tree, and how to do it in C. I figure, if I can show how to write one in C then that'll demonstrate I'm not just a Java dude with no hard core metal background.

The guy is stunned. Like I opened a bag of fresh durian in the interview room. He looks at the board, and stammers, "Uh uh I was kind of looking for something about the Boyer-Moore search algorithm? Do you know that?" I screw up my face a little and say, "Yeah but, like 10 years ago." He shakes his head, grabs his stuff, and gets up saying, "Alright, well I'll let everyone know what I think."

A few minutes later in walks the next interviewer. He looks up at the white board, chuckles and scoffs at me, then asks me another C++ template meta programming question that I couldn't answer. I did not get the job.