Amazon Interview Question
Software Engineer / DevelopersTeam: Intern
Country: United States
Interview Type: In-Person
Returns the whole list of common substrings in the given two strings...
public Set<String> getLCS(String s1, String s2)
{
if(s1 == null || s2 == null)
return null;
int len1 = s1.length(), len2 = s2.length();
int[][] array = new int[len1 + 1][len2 + 1];
int longest = 0;
Set<String> substrings = new TreeSet<String>();
for(int i = 0; i < len1; i++)
{
for(int j = 0; j < len2; j++)
{
if(s1.charAt(i) == s2.charAt(j))
{
int v = array[i][j] + 1;
array[i + 1][j + 1] = v;
if(v > longest)
{
longest = v;
}
if( v == longest)
{
substrings.add(s1.substring(i - v + 1, i + 1));
}
}
}
}
return substrings;
}
in O(mn) can be done but it will be naive approach.
the other way is to use kmp .... but we have to first generate all the pattern of second string of contniues character of len(m to 2)
then find that pattern in the first string
this will again take O(mn) in worse case
There are ways to beat O(mn), but they are quite nontrivial.
You could use a rolling hash algorithm to compare all strings of a chosen size k (with high probability of yielding a correct answer, at least) in O(m + n) expected time. Since you don't know the size of the largest string, you would do a binary search on the size of it. That is, you'd first try making a match of size min (m, n)/2 (for example), and if that fails you'd try min(m, n) / 4, and if that finds a match you'd try min(m, n) *3 / 8, etc. You'd need a total of about O((m+n) log(m+n)) time.
Create suffix tree from list1. Check for all suffixes from list2 using created suffix tree.
Use Hashmap , in hashmap key is character and value is a linkedlist storing ocurrences of that character.
Now keeps searching the hashmap for cosecutive matches .
will work in O(n) time..
XOR the contents of the two lists. and store the result in third list, this can be done in O(n) time. Now iterate the list for max no of 0's occuring together.. this can be done in O(n) time again and hence total time should O(2n) which is equivalent to O(n)...
XOR the contents of the two lists. and store the result in third list, this can be done in O(n) time. Now iterate the list for max no of 0's occuring together.. this can be done in O(n) time again and hence total time should O(2n) which is equivalent to O(n)...
public static String testLCS(String a, String b){
int maxleng = 0;
int maxbj = 0;
int[] buffer1 = new int[b.length()];
int[] buffer2 = new int[b.length()];
for(int i = 0; i<a.length();i++){
buffer2[0]=a.charAt(i)==b.charAt(0)?1:0;
if(buffer2[0]>maxleng){
maxleng = buffer2[0];
maxbj=0;
}
for(int j = 1; j<b.length(); j++){
buffer2[j]=a.charAt(i)==b.charAt(j)?(buffer1[j-1]+1):0;
if(buffer2[j]>maxleng){
maxleng = buffer2[j];
maxbj=j;
}
}
for(int t = 0; t<buffer1.length;t++){
buffer1[t]=buffer2[t];
}
}
return maxleng==0?"":b.substring(maxbj-maxleng+1,maxbj+1);
}
if requires O(n) space
public static String testLCS(String a, String b){
int maxleng = 0;
int maxbj = 0;
int[] buffer1 = new int[b.length()];
int[] buffer2 = new int[b.length()];
for(int i = 0; i<a.length();i++){
buffer2[0]=a.charAt(i)==b.charAt(0)?1:0;
if(buffer2[0]>maxleng){
maxleng = buffer2[0];
maxbj=0;
}
for(int j = 1; j<b.length(); j++){
buffer2[j]=a.charAt(i)==b.charAt(j)?(buffer1[j-1]+1):0;
if(buffer2[j]>maxleng){
maxleng = buffer2[j];
maxbj=j;
}
}
for(int t = 0; t<buffer1.length;t++){
buffer1[t]=buffer2[t];
}
}
return maxleng==0?"":b.substring(maxbj-maxleng+1,maxbj+1);
}
if requires O(n) space
public static void main(String[] args) {
String s1 = "abcrfghwetf", s2="abrfghwwetxyab";
int start =0, end = 1, max =0, maxx = 0;
int fstart = 0, fend=0;
while(end < s1.length()) {
if(s2.contains(s1.substring(start, end))) {
if(maxx < (end - start)) {
fstart = start;
fend = end;
}
end++;
max++;
} else {
if(max > maxx)
maxx = max;
max = 0;
start++;
end = start+1;
continue;
}
}
System.out.println(s1.substring(fstart, fend));
}
char str1[] = "abcrfghwetf";
char str2[] = "abrfghwwetxyab";
int max, i, j, l1, l2, cnt, sovi, sovj;
max=0;
l1=strlen(str1);
l2=strlen(str2);
for(i=0; i<l1 ; i++)
{
cnt=0;
for(j=i; j<l2 ; j++)
{
if((str1[i]==str2[j]))
{
cnt++;
i++;
j++
}
else
break;
}
if(cnt>max)
{
max=cnt;
sovi=i;
sovj=j;
}
}
printf("\n str: %s", str1+i-cnt);
String s1 = "abcrfghwetf";
String s2 = "abrfghwwetxyab";
String result = "";
int len1 = s1.length();
for(int i =0;i<len1;i++){
for(int k=1;k+i<len1;k++){
String s11 = s1.substring(i, i+k+1);
if(s2.contains(s11) == true ) {
if(result.length() < s11.length())
result = s11;
}
}
}
System.out.println("Result - "+result);
static string GetLongestCommonStr(string str1, string str2)
{
string result = string.Empty;
int len1 = str1.Length, len2 = str2.Length, maxcommon = 0;
for (int i = 0; i < str1.Length; i++)
for (int j = 0; j < str2.Length; j++)
{
if (str1[i] == str2[j])
{
int start1 = i;
int start2 = j;
int count = 1;
while (start1 + 1 < len1 && start2 + 1 < len2 && str1[++start1] == str2[++start2])
count++;
if (count > maxcommon)
{
maxcommon = count;
result = str1.Substring(i, start1-i);
}
}
}
return result;
}
hello aaz,
The most efficient algorithm would be finding the longest common substring using the Generalised Suffix Trees by using Ukkonen's algorithm. did the interviewer ask you to write the program for this ? or just give the Idea / algorithm/ pseudocode ? It's a big program to even construct a generalised suffix tree for both strings.
Thank you,
I have written the program in C#...see if it works..m not sure about the complexity..may b O(n)
static void Main(string[] args)
{
List<Char> list1 = new List<char>() {'a','c','d','r','e','g','t' };
List<Char> list2 = new List<char>() { 'a', 'c', 'w', 'r', 'e', 'g', 't','f' };
int count = 0, max = 0, final = 0;
if (list1.Count <= list2.Count)
{
count = list1.Count;
for (int i = 0; i < count; i++)
{
if (list1[i] == list2[i])
max++;
else
{
final = max;
max = 0;
}
}
}
final = max;
Console.WriteLine("Final: {0}", final);
}
public static void main(String[] args) {
System.out.println(getLCS("abcrfghwetfxy","abrfghwwetfxyab",""));
}
public static String getLCS(String A,String B,String max){
String currCS=max;
if (!Utils.isValidNonEmptyString(A)||
!Utils.isValidNonEmptyString(B))
return max;
//case 1 : A[i]==A[j]
if (A.charAt(0)==B.charAt(0))
{
currCS+=A.charAt(0);
currCS = getLCS(A.substring(1),B.substring(1),currCS);
if (currCS.length()>max.length()) max=currCS;
}
else{
String lstr = getLCS(A.substring(0),B.substring(1),"");
String rstr = getLCS(A.substring(1),B.substring(0),"");
if (lstr.length()>max.length()) max= lstr;
if (rstr.length()>max.length()) max= rstr;
}
return max;
}
Isn't the common intersection in your example "rfghw"
- Dev February 29, 2012