## Amazon Interview Question for Interns

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 5 vote

It can be found in linear time using a suffix tree. The algorithm is described in Algorithms on Strings, Trees and Sequences, section 7.4.

Suppose the strings to match are str1 and str2. The algorithm works as follows: first, build the generalized suffix tree for both strings. If you're not familiar with the concept, it's basically a suffix tree for both str1 and str2, that is, the same tree stores both the suffixes of str1 and str2. The only difference when compared with a traditional suffix tree is that the leafs in a generalized suffix tree can have different terminators (there is one terminator for each input string). So, for example, if str1 has size M and str2 has size N, we will have M+1 leafs with the terminator for str1 - let it be \$1 - and N+1 leafs with the terminator for str2 - let it be \$2.

For this problem, the generalized suffix tree traditional algorithm is modified so as to keep track of which terminators are in a given subtree. An internal node is marked with a 1 if there is at least a leaf below that contains the terminator \$1; we do the same thing for str2 and \$2.

The generalized suffix tree can be built in linear time using Ukkonen's algorithm.

Now, with the generalized suffix tree, the problem is reduced to finding the internal node with the largest string-depth that was marked with both a 1 and a 2, since internal nodes marked twice represent common substrings. So, just traverse the tree and visit every node to find the deepest one that meets such criteria. Once found, the longest common substring corresponds to the string path of that node.

It is considerably easier to understand and explain when in a whiteboard -- this is very well suited for an in-person interview.

I do believe that the point of the question is to have you explain the algorithm and show that you understand suffix trees and their construction, but I think that implementing it in the timespan of an interview is extremely hard, if not impossible. Suffix tree construction is a hard topic and coming up with bug-free code is not trivial.

Comment hidden because of low score. Click to expand.
0

Correction: No, this is NOT well suited for an in-person interview.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.