Amazon Interview Question for Software Engineer / Developers


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"

- Dev February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dev February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- xiuxiu March 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hello world March 03, 2012 | Flag
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

- NaiveCoder February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi March 06, 2012 | Flag
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.

- Anonymous February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct.

- Snehasish Barman February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mukul.dce March 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Meena March 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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

- Soba March 02, 2012 | Flag Reply
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..

- yogeshhan February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does not work for strings:
xyayz
axyza

- Anonymous February 29, 2012 | Flag
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

will not work for ... abcdefxyz
xyzadfghi

- yogeshhan February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ian March 01, 2012 | Flag
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
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)...

- Mebin Jacob February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pandit March 05, 2012 | Flag
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.

- m@}{ February 29, 2012 | Flag Reply
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.

- m@}{ February 29, 2012 | Flag Reply
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

- TaoS March 01, 2012 | Flag Reply
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

- TaoS March 01, 2012 | Flag Reply
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));

}

- raptor March 03, 2012 | Flag Reply
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);

- CheckThisResume.com March 05, 2012 | Flag Reply
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.

- crack_it March 05, 2012 | Flag Reply
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);

- Anonymous March 11, 2012 | Flag Reply
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;
}

- Anonymous March 14, 2012 | Flag Reply
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,

- viv March 18, 2012 | Flag Reply
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);
        }

- krish March 31, 2012 | Flag Reply
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;
}

- Mugunth July 17, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

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.

Learn More

Mock Interviews

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.

Learn More