Amazon Interview Question for Developer Program Engineers


Country: United States




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

Not that you would actually be able to code this in time but an algorithm to solve this in linear time is:

1) Construct a suffix tree using Ukkonen algorithm
2) Starting at top, take the branch that starts with the first char in the string.
3) Traverse down, look for nodes that have a branch to end of string and another char.
Whenever you have found one of these node, you have found a border.
4) Find the deepest node that is a border that is less than or equal to length of string divided by 3.
5) That will be the answer.

- Some guy July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, thinking about this a bit more, a suffix tree would larger than O(N) space. However, we don't need a full suffix tree to solve this problem. A suffix tree with only the full word branch is necessary so its probably still doable in O(N) space, I'm just not sure how to construct such a suffix tree.

- Some guy July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Some guy

Nice solution! A few ideas that I would like to contribute..

Build a 2 suffix trees T1 and T2.

1. Build T1 for substring(n/3, 2n/3) and T2 for substring(2n/3, n).
2. Look for prefixes of substring(1,n/3) in both the T1 and T2.
3. The longest such prefix of substring(1,n/3) that is present both in T1 and T2 is a border with maximum length and having an occurrence count >=3

- Murali Mohan July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

@Some guy & Ayahuasca
Nice! However let me challenge your idea of using tries :)

How can you efficiently and correctly solve the "non-overlap" criteria? <Some guy>'s solution does not address the non-overlap criteria between the head string and the middle string (if I understand correctly, at least not in a very efficient way), while <Ayahuasca>'s solution is, pardon me if I am wrong, not correct: the desired string may appear twice in the range (1,n/3) and once in (2n/3,n), right?

- Chih.Chiu.19 July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

just one doubt , question says that the input could be 1 million characters , and creating the suffix tree for it will be too much also suffix tree we use when text is same and pattern is changing whereas kmp we use when pattern is same and text is changing.

- Anonymous September 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1 : use stack to identify the sample border cases -- Space O(N/2) Time O(N)
Step 2 : if a border exist perform KMP for the identified border and check the stating position .if there are three disctinct starting position print the border
- Space O(max(border.length)) - time O(N);

border identifying can also be done with a reverse string function performing validations from both ends

- Rohit July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

take two pointers one from start of string and other from end, match the charters, if matched then pass the strings to kmp algorithm where input string will be from index 0 to length -1, if kmp return true then again pass it to kmp where input string will be end point of previous match . and count the matches,
if match occurs three times then this will be the one such string,
then again take more characters and try it. if match found for this then replace it with previous one. when matched failed then last string will be longest string for borders.

- kaushal July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why not:

again pass it to KMP and
again pass it to KMP and
again pass it to KMP and
...???

- Anon July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anon for checking three occurrences...

- kaushal yadav July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
int main()
{
    char str[]="ababab";
    int n,i,j,l,k,count,max=0;
    l=strlen(str);

    for(i=0;i<(l/2);i++)
    {   j=l-1-i;
        k=0;
        count=0;
        while(k<=i&&j<l)
            {
                if(str[k]==str[j])
                  count++;
                    k++;
                    j++;

            }
            if(count==(k))
            {
              if(isasubstring(str,k,l-(2*(k))))
                   if(max<count)
                    max=count;

            }
    }
    printf("length of longest border is : %d",max);

    return 0;
}
isasubstring(char *a,int s,int n)
{
    int i,j;
    char *temp;
    char *pattern=malloc(sizeof(char)*(s+1));
    char *input =malloc(sizeof(char)*(n+1));
    memcpy(pattern,a,s);
    pattern[s]='\0';
    j=0;
    for(i=s;i<=s+n-1;i++)
    {
        input[j]=a[i];
        j++;
    }
    input[j]='\0';
    //printf("%s--- %s\n",input,pattern);
   temp=strstr(input,pattern);
   if(temp)
    return 1;
   else
    return 0;
   }

- kaushal yadav July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am using modified version of KMP algorithm as follows:

As the border should have 3 non-overlapping occurrences, the maximum length of this border can be len /3.

1) I am computing LPS array for the largest suffix possible.
The last index of suffix_lps array will tell me the longest suffix border found in the given string.

2) if longest suffix border is 0, then return 0 as there is no suffix that matches prefix.
Else compute second_lps array for the 2nd occurence. The 2nd occurence can happen anywhere from index 1 to index len-2.

3) Then I will look in the second_lps to see if there is any border of length same as suffix border and also that there is no over lap in the index of 2nd border and suffix border.

Here is the code:

int len = instr.length();	
	int suf_start_idx = (len%2) ? 2*len/3 +1 : 2*len/3;
	string suffix = instr.substr(suf_start_idx);
	int max_suf_len = len - suf_start_idx;
	
	int suffix_lps[max_suf_len];
	int second_lps[len - 1];
	
	string prefix = instr.substr(0, len/3);
	computeLPSarray(suffix, max_suf_len, prefix, suffix_lps);
	if (suffix_lps[max_suf_len-1] == 0)
		ret_val = 0;
	else
	{
		computeLPSarray(instr.substr(1), len-1, prefix, second_lps);
		int idx_suf_start_match = len - suffix_lps[max_suf_len-1];
		for(int i =  0; i < len-1; i++)
		    if ((second_lps[i] == suffix_lps[max_suf_len-1]) && (i < idx_suf_start_match))
			{
				ret_val = second_lps[i];
				break;
			}
	}
		
	cout << ret_val << endl;

suf_start_idx = (len%2) ? 2*len/3 +1 : 2*len/3;
string suffix = instr.substr(suf_start_idx);
pattern = instr.substr(0, len/3);
computeLPSarray(suffix, max_suf_len, pattern, suffix_lps);

- king July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested following code on linux machine

#include <iostream>
#include <string.h>
using namespace std;

int getBorder(const char* sInput)
{
  int nLen = strlen(sInput);
  int iFHIdx = nLen/2;
  int iStartIdx = -1;
  int iEndIdx = nLen-1;
  bool flag = false;
  while(iFHIdx >= 0)
  {
    // No match, start looking after iStartIdx - 1;
    if( sInput[iEndIdx] != sInput[iFHIdx])
    {
      if(flag == true)
        iFHIdx = iStartIdx - 1;
      else
      {
        iStartIdx = -1;
      }
      iFHIdx--;
      iEndIdx = nLen-1;
      flag = false;
    }

    if(sInput[iEndIdx] == sInput[iFHIdx])
    {
      if( flag == false)
        iStartIdx = iFHIdx;
      iFHIdx--;
      iEndIdx--;
      flag = true;
    }
  }
  char* sBorder = NULL;

  if(flag)
  {
    sBorder = new char[iStartIdx+2];
    cout << "Input string:" << sInput << " Border:" << iStartIdx+1 << endl;
    memcpy(sBorder, sInput, iStartIdx+1);
    cout << "Border: " <<  sBorder << endl;
  }
  else
  {
    cout << "Input string:" << sInput << " Border:" << 0 << endl;
    return 0;
  }
  
  char* sSubStrStart = strstr(sInput + iStartIdx+1, sBorder);
  cout << "String: " << sSubStrStart << endl;
  if(sSubStrStart != NULL
     && strlen(sSubStrStart) != iStartIdx+1 )
  {
    cout << "Sub string found" << endl;
    return iStartIdx+1;
  }
}

int main()
{
  //getBorder("baxxxxxa");
  //getBorder("baxxxxxb");
  //getBorder("baxxxxba");
  getBorder("abcabcabxxxabcabxxxxxxpqrsabcab");  
 
}

- PT July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please correct me if there is mistake in the following code-snippet:

totalCnt=0;
for(i=0;i<=n/2;i++)
{
if(Compare(str.substr(0,i),str.substr(n-i-1,n-1))==0) // i.e., there is a match
{
if(KMP(str.subtr(0,i),str) >= 3)
{
puts(str.substr(0,i));
totalCnt++;
}
}
}

- Anonymous July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
this is my solution that works for all my tests but not for Codility. Can you please give me an example for which this code is wrong?

public static int solution(String S) {
		// The string must be at least 3 chars
		if (S == null || S.length() < 3) {
			return 0;
		}
		// We transform the String into an array of char
		final char[] input = S.toCharArray();
		final int maxCandidateLength = input.length / 3;
		// We try to search the first char into all the array
		int[] candidateIndexes = new int[input.length];
		int candidateNumber = 0;
		int lastIndex = 0;
		for (int i = 0; i < input.length ; i++ ){
			if (input[i] == input[0]) {
				candidateIndexes[candidateNumber++] = i;
				lastIndex = i;
			}
		}
		// If the number of items is less that 3 we return 0
		if (candidateNumber < 3) {
			return 0;
		}
		int maxLength = 0;
		// Here we have at least 3 items with 1 char so we set as candidate the 1
		if (lastIndex == input.length - 1){
			maxLength = 1;
		}
		// We have to test the others
		int offset = 1;
		int[] tmpIndexes = new int[candidateNumber];
		int tmpNumber = 0;
		while (offset <= maxCandidateLength) {
			char tocheck = input[offset];
			tmpIndexes[tmpNumber++] = 0;
			for (int j = offset ; j < candidateNumber; j++) {
				int newIndex = candidateIndexes[j] + offset;
				if (newIndex >= input.length) {
					// Here we have reached the end so we have found a candidate
					if (offset > maxLength){
						maxLength = offset;
					}
					continue;
				}
				if (input[newIndex] == tocheck) {
					tmpIndexes[tmpNumber++] = candidateIndexes[j];
				}
			}	
			if (tmpNumber < 3) {
				// In this case we have finished because we don't have 3 occurrences
				break;
			}
			candidateNumber = tmpNumber;
			candidateIndexes = tmpIndexes;
			tmpNumber = 0;
			offset++;
		}
		return maxLength;
	}

- Luck September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class ThreeString {
	public int solve(String S) {
		//modified KMP
		int[] pi = new int[S.length()];
		int matched = -1;
		pi[0] = -1;

		for (int i = 1; i < S.length(); i++) {
			while (matched != -1 && S.charAt(i) != S.charAt(matched + 1)) {
				matched = pi[matched];
			}
			if (S.charAt(i) == S.charAt(matched + 1)) {
				matched++;
			}
			pi[i] = matched;
		}
		int possible = pi[S.length() - 1];
		while (possible != -1 && possible + 1 > S.length() / 3) {
			possible = pi[possible];
		}
		if (possible == -1) {
			return 0;
		}

		pi = Arrays.copyOf(pi, possible + 1);

		// 012345678
		// aaaaaaaaa
		// 012
		matched = -1;
		int max = 0;
		for (int i = 0; i < S.length(); i++) {
			while (matched != -1 && S.charAt(i) != S.charAt(matched + 1)) {
				matched = pi[matched];
			}
			if (S.charAt(i) == S.charAt(matched + 1)) {
				matched++;
			}
			max = Math.max(
					max,
					Math.min(Math.min(i - matched, matched + 1), S.length() - 1
							- i));
			if (matched == pi.length - 1) {
				matched = pi[matched];
				max = Math.max(
						max,
						Math.min(Math.min(i - matched, matched + 1), S.length()
								- 1 - i));
			}
		}
		return max;
	}

	public static void main(String[] args) {
		ThreeString ts = new ThreeString();
		String[] S = { "123451234512345", "a", "aa", "aaa", "aaaa", "aaaaa",
				"aaaaaa","aaaaaaaa","aaaaaaaaa"};
		for (int i = 0; i < S.length; i++) {
			System.out.println(S[i]+"=  "+ts.solve(S[i]));
		}
		StringBuilder sb=new StringBuilder("");
		for(int i=0;i<200;i++){
			sb.append("a");
		}
		for(int i=0;i<300;i++){
			sb.append("b");
		}
		for(int i=0;i<200;i++){
			sb.append("a");
		}
		System.out.println(ts.solve(sb.toString()));
	}
}

- jicheninsjtu July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This code work don't good. S= "barbararhubarb" return 3, not 1.

- Pawel July 22, 2013 | Flag


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