Amazon Interview Question Interns
Country: India
Interview Type: In-Person
is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
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.
- 010010.bin June 09, 2015Suppose 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.