Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

Team: Intern
Country: United States
Interview Type: In-Person

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

Isn't the common intersection in your example "rfghw"

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

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;
}``````

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

the question is for contiguous common intersection...and ask for efficient algo.

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

you can make a small change to my algorithm here, so that it will collect only the largest string and then check for the contiguous common intersection. That should give you the answer

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

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

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

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.

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

Create suffix tree from list1. Check for all suffixes from list2 using created suffix tree.

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

Correct.

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

What is the complexity of building a suffix tree? I guess o(n2)

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

The complexity of building suffix trees is O(n) by McCreight's Algorithm.

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

This is a variant of longest common substring, check wiki please.

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

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..

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

Does not work for strings:
xyayz
axyza

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

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)...

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

will not work for ... abcdefxyz

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

XORing may not help.
It does not take into consideration the placement of the sub-string in the list.

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

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)...

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

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)...

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

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)...

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

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)...

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

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)...

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

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)...

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

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)...

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

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)...

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

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)...

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

How the complexity is O(n) .
You are rotating whole list that will take O(n) and these rotations will be done n times in worst case.
So the complexity is O(n^2).

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

Create suffix tree from list1. Check for all suffixes from list2 using created suffix tree.

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

Create suffix tree from list1. Check for all suffixes from list2 using created suffix tree.

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

``````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

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

``````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

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

``````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));``````

}

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

``````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);``````

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

use a max heap based on length of the substring which also stores the nd end index of the string.

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

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);

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

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;
}

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

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,

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

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);
}``````

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

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;
}

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.