Amazon Interview Question


Country: India




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

public String findLongestSubstring(String s1, String s2) {
        List<Integer> occurs = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(s2.length()-1)) {
                occurs.add(i);
            }
        }
        
        Collections.reverse(occurs);
        
        for(int index : occurs) {
            boolean equals = true;
            for(int i = index; i >= 0; i--) {
                if (s1.charAt(index-i) != s2.charAt(s2.length() - i - 1)) {
                    equals = false;
                    break;
                }
            }
            if(equals) {
                return s1.substring(0,index+1);
            }
        }
        
        return null;
    }

- Jordi Marés Soler October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

def FindLongestSubString(s1, s2):

    if s1 == "" or s2 == "" or s1 == "\0" or s2 == "\0":
        return ""
    else:
        s1 = s1.lower()
        s2 = s2.lower()
        if s1 == s2:
            return s1
        else:
            if len(s1) < len(s2):
                i = len(s1)
                while i>0 and not s2.endswith(s1[0:i]):
                    i -= 1
                if i>0:
                    return s1[0:i]
                else:
                    return ""    
            else:  
                i = 0
                while i<len(s2) and not s1.startswith(s2[i:]):
                    i += 1
                if i<len(s2):
                    return s2[i:]
                else:
                    return ""

- Meena October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

These are not optimal solution and inefficient ,O(n^2) although simple. I would rather go for obvious modifications into KMP String matching algorithm's prefix function calculation in O(n) time.

- zahidbuet106 December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

what about

public class Solution {
	
	public String prefix(String sa, String sb){
		int length = -1,temp = -1;
		for(int i = sa.length() -1 ;i>=0;i--){
			length = -1;temp = -1;
			if(sa.charAt(i)==sb.charAt(sb.length()-1)){
				temp = compareStrings(sa.substring(0,i), sb.substring(0,sb.length()-1));
				if(temp >0){
					length = 1 + temp;
					break;
				}
			}
		}
		
		if(length > 0)
			return sa.substring(0,length);
		return "";
		
	}
	
	public int compareStrings(String s1,String s2){
		int la = s1.length()-1, lb = s2.length() -1;
		if(s1.length()==0) return 0;
		if((lb<0)&&(la>=0)) return -1;
		if(s1.charAt(la)==s2.charAt(lb)){
			la = compareStrings(s1.substring(0,la), s2.substring(0,lb));
			if(la < 0 )
				return -1;
			else 
				return 1 + la;
		}
		else
			return -1;
	}
	
	public static void main(String[] args) {
		String s1 = "AAAAB";
		String s2 = "AAAAAB";
		
		System.out.println("first string is : "+ s1);
		System.out.println("second string is : "+ s2);
		
		Solution obj = new Solution();
		String lcs = obj.prefix(s1, s2);
		
		System.out.println("The longest substring is : "+lcs);

	}
}

- ranjith October 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static String longestPrefixSuffix(String s1, String s2) {
        final StringBuilder builder = new StringBuilder();
        int s1p = 0;
        int s2p = 0;
        while (s1p < s1.length() && s2p < s2.length()) {
            if (s1.charAt(s1p) == s2.charAt(s2p)) {
                builder.append(s1.charAt(s1p));
                s1p++;
            } else {
                s1p = 0;
                builder.setLength(0);
            }
            s2p++;
        }
        return builder.toString();
    }

We can create two pointers, for the first and the second string. Increment second each iteration, first increment if there is the matching, if matching is not present - reset pointer and temporary result.

- anonymous October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good approach but will fail for
s1: ABCADE
s2: ABCABC

so -1

- niraj.nijju October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Nice catch.
It's simple to fix that changing the while loop:

while (s1p < s1.length() && s2p < s2.length()) {
            if (s1.charAt(s1p) == s2.charAt(s2p)) {
                builder.append(s1.charAt(s1p));
                s1p++;
                s2p++;
            } else {
                s1p = 0;
                s2p -= s1p + 1;
                builder.setLength(0);
            }
        }

Unfortunately the complexity is growing from nice O(n) to O(n^2) in worst case.

- anonymous October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

grow up man

try for
AAAAB & AAAAAB

- niraj.nijju October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

try for
AAAABX & AAAAAB

- niraj.nijju October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

oh

while (s1p < s1.length() && s2p < s2.length()) {
            if (s1.charAt(s1p) == s2.charAt(s2p)) {
                builder.append(s1.charAt(s1p));
                s1p++;
                s2p++;
            } else {
                s2p = s2p - s1p + 1;
                s1p = 0;
                builder.setLength(0);
            }
        }

Working for the all above examples.
Do you have a full set of test cases?

- anonymous October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

/**
 * Java
 */
public class PrefixSuffix {

	public PrefixSuffix() {
		super();
	}
	
	public static String preSuf(String s1, String s2) {
	
		String match = "";
		int maxLen = (s2.length() > s1.length()) ? s1.length() : s2.length();
		
		for (int i=1; i<=maxLen; i++) {
			if (s1.substring(0,i).equals(s2.substring(s2.length()-i))) {
				match = s1.substring(0,i);
			}
		}
				
		return match;

	}
	
	public static void main(String[] args) {
		String s1 =    "gggbingbinghello"; 
		String s2 = "abcdbingasdfgggbing";
		
		String s3 = PrefixSuffix.preSuf(s1, s2);
		System.out.println("Answer is: " + s3);
	}
}

- Daniel G October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

-1 for O(n^3)

- niraj.nijju October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

So, Anyone can write code for this in O(n).. I mean is there a soln for this in o(n)??

- ganesh October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no, I don't think so

I have made a solution having worst case O(n^2).
and the answer by Jordi Marés is also O(n^2) in worst case

- niraj.nijju October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is not a solution in o(n) (that's little-O) because you have to look at all the characters of the string you're given.

As far as coding in O(n) (big-O), it's not that easy (though possible). I'd be interested in hearing how you solved it.

- eugene.yarovoi October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene.yarovoi

no that's not in O(n), i have done in O(n^2)
have done similar as Jordi Marés Soler with little more optimization,
--no list
--no sorting of list
--not calculating other indexes after getting my answer
(putting my solution here)

- niraj.nijju October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, it can be solved in O(n).

Construct a suffix tree for string s2 in O(n) time using Ukkonen's algorithm for constructing suffix trees - O(n) time and O(n) extra space.

Search string s1 in the suffix tree constructed in above step - O(n) time

The longest matched prefix of string s1 is the required substring.

Total time - O(n) and extra space used is O(n)

- EOF October 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

yeah you can do it in O(n) using KMP string matching algorithm. Use the prefix function in KMP algorithm and do the tweaks.

- zahidbuet106 December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>


char *findSubstring(const char *str1, const char*str2) 
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    
    // find maximum length of common substring
    int n = 1; 
    int max = 0;
    while (n <= len1 && n <= len2) {
        if (!strncmp(str1, str2 + len2 - n, n)) max = n;
        n++;
    }

    // create substring
    char *output = (char*)malloc(max+1);
    strncpy(output, str1, max);
    output[max] = '\0';

    return output;
}

int main()
{
    const char *str1 = "ABCABCzzzzzzzzzzzzzzzzzzzzzzzzzzz";
    const char *str2 = "xxxxxxxxxxxxxxxABCABC";

    char *output = findSubstring(str1, str2);

    printf("[%s]\n", output);
    free(output);

    return 0;
}

- Krzysztof.G October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think this algo will work :
1.scan s1 from back and stop when u find matching character to last character of s2.
2.start back scan of s1 and s2 frm there till both match
3.if now we reach -1 for s1 then we find prefix as continue from there with above steps
int i=s1.length()-1,j;
while(i!=-1)
{ for(;i>=0;i--)
if(s1[i]==s2[s2.length()-1])
break;
j=s2.length()-1;
while(i>=0 && s1[i]==s2[j])
{
i--;
j--;
}
}

- mg October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested and appears to work 100%. Added features of skipping ahead (if length stringB<stringA) & checking first and last character before checking entire string. A few more things can be done for efficiency (i.e. if len == 0 or len == 1) and error checking, but not without cheating too much and spending several hours to write the most perfect elegant solution ever.

//test the code
	public static void main(String[] args) {
		String stringA = "ABABCDEFGxxxxxxxxxxx";
		String stringB = "xxxABABCDEFG";
		
		String match = prefixSuffix(stringA, stringB);
		System.out.println("Match: "+match);
	}
	
	
	
	public static String prefixSuffix(String stringA, String stringB){
		int lenA = stringA.length();
		int lenB = stringB.length();
		
		if (lenA == 0 || lenB == 0) return ""; 
		
		int startPos = (lenA < lenB) ? lenB-lenA: 0;//can skip ahead for efficiency.
		
		for (int i = startPos; i < lenB; i++) {
			if (compareStrings(stringA, stringB, 0, i, lenB-i-1)){
				return stringA.substring(0, lenB-i);
			}
		}
		return "";
	}
	
	//helper for prefix suffix comparator.
	public static boolean compareStrings (String stringA, String stringB,int indexA, int indexB, int length) {
		//TODO throw exception if index+length out of range
		if (stringA.charAt(indexA) != stringB.charAt(indexB)) {return false;}//check first
		if (stringA.charAt(indexA+length) != stringB.charAt(indexB+length)) {return false;}//check last
		
		for (int j = 1; j < length-1; j++) {//check middle
			if (stringA.charAt(indexA+j) != stringB.charAt(indexB+j)) {return false;}//check first
		}
		return true;
	}

- Java & Tested October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested and appears to work 100%. Added features of skipping ahead (if length stringB<stringA) & checking first and last character before checking entire string. A few more things can be done for efficiency (i.e. if len == 0 or len == 1) and error checking, but not without cheating too much and spending several hours to write the most perfect elegant solution ever.

//test the code
	public static void main(String[] args) {
		String stringA = "ABABCDEFGxxxxxxxxxxx";
		String stringB = "xxxABABCDEFG";
		
		String match = prefixSuffix(stringA, stringB);
		System.out.println("Match: "+match);
	}
	
	
	
	public static String prefixSuffix(String stringA, String stringB){
		int lenA = stringA.length();
		int lenB = stringB.length();
		
		if (lenA == 0 || lenB == 0) return ""; 
		
		int startPos = (lenA < lenB) ? lenB-lenA: 0;//can skip ahead for efficiency.
		
		for (int i = startPos; i < lenB; i++) {
			if (compareStrings(stringA, stringB, 0, i, lenB-i-1)){
				return stringA.substring(0, lenB-i);
			}
		}
		return "";
	}
	
	//helper for prefix suffix comparator.
	public static boolean compareStrings (String stringA, String stringB,int indexA, int indexB, int length) {
		//TODO throw exception if index+length out of range
		if (stringA.charAt(indexA) != stringB.charAt(indexB)) {return false;}//check first
		if (stringA.charAt(indexA+length) != stringB.charAt(indexB+length)) {return false;}//check last
		
		for (int j = 1; j < length-1; j++) {//check middle
			if (stringA.charAt(indexA+j) != stringB.charAt(indexB+j)) {return false;}//check first
		}
		return true;
	}

- Java & Tested October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe not the fastest solution, but...

static String longestCommonPrefixAndSuffix(String s1, String s2) {
    String solution = s1.substring(0, Math.min(s1.length(), s2.length()));
    while (solution.length() > 0) {
      if (s2.endsWith(solution)) {
        return solution;
      }
      solution = solution.substring(0, solution.length() - 1);
    }

    return solution;
  }

- Sergey Y. October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is my solution, takes O(n)?

public static String findLongestSubstring(String s1, String s2) {

for(int i = 0; i < s1.length(); i++){
if(s2.charAt(i)==s1.charAt(0)){
if(s2.substring(i).equals(s1.substring(0,s2.length()-i))){
return s2.substring(i);
}
}
}
return null;
}

- Steve October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

main()
{
char str1[]="abcdeee";
char str2[]="sssssabc";
int i=0,j,k,l;
int n=strlen(str2);
if(strlen(str1)<strlen(str2)){
n=strlen(str1);
}
k=0;
l=0;
for(i=0;i<n;i++){
j=strlen(str2)-n+i;
if(str1[l++]!=str2[j]){
i=k;
k++;
l=0;
}
}
printf("%s",str2+strlen(str2)-n+k);
}

- vimalesan.a October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String PrefixSuffix(String stringA, String stringB)
        {
            for (int i = stringA.Length; i > 0; i--)
            {
                string longestMatchingSubstring = stringA.Substring(0, i);
                int suffixStartPosition = stringB.LastIndexOf(longestMatchingSubstring);
                if ((suffixStartPosition != -1) && (suffixStartPosition + i == stringB.Length))
                    return longestMatchingSubstring;
            }
            return "No Match Exists";
        }

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

def longest_sub(s1, s2):
    if s1 == None or s2 == None:
        return None
    longest = ''
    lvl = 1
    while lvl <= len(s1) and lvl<= len(s2):
        if s1[:lvl] == s2[lvl:]:
            longest = s1[:lvl]
            lvl += 1
        else
            break
    return longest

- null404 October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given s1 and s2, where we are interested in finding the longest prefix of s1 that matches a suffix of s2, we can do the following:
1- Build a suffix tree on all the suffixes of s2: i.e. s2[i..n] for i=0..n-1 and n is size of s2. This takes O(n)
2- Traverse the suffix tree using s1: if at some point we reach a leaf, we have found the solution. If the traversal ends at a non-leaf node, there is no such suffix.

- pirooz October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void LongestPrefixSufixMatch(char *s1, char *s2)
{
	if(!*s1 || !*s2)
		return;
	int n1=strlen(s1);
	int n2=strlen(s2);

	int l=n1<=n2?n1:n2;

	int len,i,I,k,end=-1;
	int max=INT_MIN;

	for(i=0;i<l;i++)
	{
		if(s1[i]==s2[n2-1])
		{
			I=i;
			k=0;
			len=0;
			while(I>=0 && s1[I]==s2[n2-1-k])
			{
				I--;
				k++;
				len++;
			}
			if(len>max)
			{
				max=len;
				end=i;
			}
		}
	}
	for(i=0;i<=end;i++)
		printf("%c",s1[i]);
    printf("\n");
}

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

#include<stdio.h>


char * long_sub_str( char *str1 , char *str2 )
{

    int str1_len    =   strlen(str1);
    int str2_len    =   strlen(str2);

    char *stPtr = str1, *enPtr = str2+str2_len ;

    int len = (str1_len > str2_len) ? str1_len : str2_len ;
    int done    = 0, str_len = 1;
    while( str_len < len )
    {
        done = strncmp(str1, enPtr-str_len, str_len) ? done : str_len;
        str_len++;
    }

    return enPtr-done;
}

int main()
{
    char *str1 = "ABCDee";
    char *str2 = "xxxxxxxxxxxxxxxxxxxxABC";

    char *lstr = long_sub_str(str1,str2);

    printf("%s", lstr);
}

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

#include<stdio.h>


char * long_sub_str( char *str1 , char *str2 )
{

    int str1_len    =   strlen(str1);
    int str2_len    =   strlen(str2);

    char *stPtr = str1, *enPtr = str2+str2_len ;

    int len = (str1_len > str2_len) ? str1_len : str2_len ;
    int done    = 0, str_len = 1;
    while( str_len < len )
    {
        done = strncmp(str1, enPtr-str_len, str_len) ? done : str_len;
        str_len++;
    }

    return enPtr-done;
}

int main()
{
    char *str1 = "ABCDee";
    char *str2 = "xxxxxxxxxxxxxxxxxxxxABC";

    char *lstr = long_sub_str(str1,str2);

    printf("%s", lstr);
}

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

public static String getLongestPrefixSuffix(String str1, String str2) {
		String temp1;
		int str2Length = str2.length();

		for (int i = str1.length() - 1; i >= 0; i--) {
			temp1 = str1.substring(0, i);
			if ((str2.indexOf(temp1) + temp1.length()) == str2Length) {
				return temp1;
			}
		}
		return null;
	}

- rajeevkrishnanv October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static string LongestPrefixAndSuffix(string s1, string s2)
		{
			if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
				return String.Empty;

			for (int i = 0; i < s2.Length; i++)
			{
				// search for a potential 'start' character in the
				// suffix string
				if (s2[i] == s1[0] &&
					String.Compare(s1,0,s2,i, s2.Length - i) == 0)
				{
					return s2.Substring(i);
				}
			}

			return String.Empty;
		}

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

This is first step in KMP algorithm. Same as building the KMP table. Following is o(n) time complexity algo where n is number of characters in second string.

public static String longestPrefix ( String first, String second ) {
		if ( first == null || second == null || first.isEmpty() || second.isEmpty() ) return "";
		
		if ( first.equals(second)) return first;
		
		char[] firstChars = first.toCharArray();
		char[] secondChars = second.toCharArray();
		
		int matched = 0;
		for ( int j=1; j<secondChars.length;) {
			if ( firstChars[matched] == secondChars[j]) {
				matched++;
				j++;
			} else {
				if ( matched > 0 ) {
					matched=0;
				} else {
					j++;
				}
			}
		}
		
		if ( matched > 0 ) return second.substring(second.length()-matched, second.length());
		else return "";
	}

- sp November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PrefixSuffix {

public static void main(String[] args) {
String A = "ABCDEF";
String B = "ABCABC";

System.out.println(prefixSuffix(A,B));

}

public static String prefixSuffix(String A, String B)
{
int x = 0; // index for A
int marker = -1; // index where the suffix starts on B

for(int y=0; y<B.length(); y++)
{
char atA = A.charAt(x);
char atB = B.charAt(y);
if(atA == atB)
{
if(x == 0) marker = y;
x++;
}
else
{
x = 0;
if(marker != -1) y--; // For a new sequence to match move back one index
marker = -1;
}
}

if(marker >=0 ) return B.substring(marker);
else return null;
}

}

- dghosh December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PrefixSuffix {

	public static void main(String[] args) {
		String A = "ABCDEF";
		String B = "ABCABC";
		
		System.out.println(prefixSuffix(A,B));

	}
	
	public static String prefixSuffix(String A, String B)
	{
		int x = 0; // index for A
		int marker = -1; // index where the suffix starts on B
		
		for(int y=0; y<B.length(); y++)
		{
			char atA = A.charAt(x);
			char atB = B.charAt(y);
			if(atA == atB)
			{
				if(x == 0) marker = y;
				x++;
			}
			else
			{
				x = 0; 
				if(marker != -1) y--; // For a new sequence to match move back one index
				marker = -1;
			}
		}
		
		if(marker >=0 ) return B.substring(marker);
		else return null;
	}

}

- dghosh December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

string preSuf(string s1, string s2){
	if (s1.size() == 0 | s2.size() == 0)
		return "string size must be greater than 0";
	int p_length = (int)min(s1.size(),s2.size());
	for (int i = p_length; i > 0; i--){
		if(s1.substr(0,i) == s2.substr(s2.size()-i,i))
			return s1.substr(0,i);
        continue;
	}
    return "common prefix/suffix not found";
}

- Forest October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

-1

it is O(n^3)

you should use String.equals()

- niraj.nijju October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

string preSuf(string s1, string s2){
	if (s1.size() == 0 | s2.size() == 0)
		return "string size must be greater than 0";
	int p_length = (int)min(s1.size(),s2.size());
	for (int i = p_length; i > 0; i--){
		if(s1.substr(0,i) == s2.substr(s2.size()-i,i))
			return s1.substr(0,i);
        continue;
	}
    return "common prefix/suffix not found";
}

- Forest October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Algorithm:
1. Search the first char of S1 in S2 (from last). If S1 prefix has consecutive duplicates (AAAB) then move backwards (from the position we just found) in S2 until we different char.
2. Now, compare S1 from beginning and in S2 from the point we got in step 1.
3. Compare till we found mismatch or end of the string(s). If we are end of S2 then the traversed string is longest sub string.

Example:
S1 = "abcdef" and S2 = "xyxabc"
1. after first step the s2 pointer points to s[3] i.e a
2. Now start compare from s1[0] and s2[3]
Since our search ends at end of S2 the longest sub string is 'abc'

Let me know, If I am missing any cases.

- Kallu October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

private static String find(String f, String s) {
char first = f.charAt(0);
int index = s.lastIndexOf((int) first);
int ind = 1;
boolean b = true;
if (index >= 0) {
for (int i = index + 1; i < s.length(); i++) {
if (f.charAt(ind) == s.charAt(i)) {
ind++;
} else {
b = false;
break;
}
}
}
return b ? s.substring(index) : "";
}

- deepk2u October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/**
	 * to find the commonRegion which is prifix of read1 as well as suffix of read2
	 * 
	 * @param read1
	 * @param read2
	 * @return String (the commonRegion)
	 */
	public String getCommonRegion(String read1, String read2){
		List<Integer> occurences = new ArrayList<Integer>();
		int maxCommonLength = read1.length()>read2.length()? read2.length() : read1.length();
		int l1 = read1.length();
		int l2 = read2.length();
		for(int i=0;i<maxCommonLength;i++){
			if(read1.charAt(0) == read2.charAt(l2-maxCommonLength+i) 
			  && (read1.charAt(maxCommonLength-i-1)==read2.charAt(l2-1))){
				int k = l2-maxCommonLength+i;
				boolean isCommomRegion = true;
				for(int j=1;k+j<l2;j++)
					if(read1.charAt(j)!=read2.charAt(k+j)){
						isCommomRegion = false;
	                    break;
						}
				if(isCommomRegion)
					return read2.substring(k);
			}
		}
		return "";
	}

- niraj.nijju October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

What about:

public String prefixSufix(String s1, String s2) {
		if (s1.isEmpty() || s2.isEmpty()) return "";

		char lastPrefixChar = s2.charAt(s2.length() - 1);
		String biggerSubstring = "";
		boolean found = false;

		while (!found) {
			int lastIndex = s1.lastIndexOf(lastPrefixChar);
			String endingSubstring = s1.substring(0, lastIndex + 1);
			if (s2.endsWith(endingSubstring)) {
				found = true;
				biggerSubstring = endingSubstring;
			} else {
				s1 = s1.substring(0, lastIndex);
			}
		}
		return biggerSubstring;
}

- Jose October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

worst method

- niraj.nijju October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

string longest_common_prefix(const string& a, const string& b)
{
      int i(0), j(0);
      while (i < a.size() && j < b.size())
      {
                if (a[i] != b[j]) break;
      }
      return i != 0 ? a.substr(0, i-1) : string(""); 
}

- Anonymous October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

not good approach, as making suffix tree but still it is O(n^2).

-1 for not returning longest one. in fact it will alwayse return Strign of zero length("") for i=0

- niraj.nijju October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

So we have 2 strings:
abcdxxxxx
xxxxxabcd

We reverse 2nd string for suffix: dcbaxxxxx

Will you find a match there? I don't think so.

- peach99 October 21, 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