## Amazon Interview Question

Technical Support Engineers**Country:**India

**Interview Type:**Written Test

If the program is going to be used only once. What the tip suggests is good enough. Taking O(nm) time, where n is the length of the longer string and m is the length of the shorter one.

If it is going to be used many times for checking different substrings, first build the surffix tree of the long string. Then checking a substring of length m only takes O(m) time.

```
public static int getSubStringStartingPosition(char[] st1, char[] st2)
{
int pos=0;
boolean flag=false;
int k=0;
for (int i=0; i<=st1.length-1; ++i)
{
if ((k <= st2.length-1) && (st1[i]==st2[k]))
{
//System.out.println("found.."+st2[k]);
if (!flag)
{
pos=i;
}
flag=true;
k++;
}
else
{
System.out.println("not found.."+st1[i]);
if (flag && k <=st2.length-1)
{
System.out.println("found an extra character in the middle..");
pos=-1;
}
}
}
return pos;
}
```

｛｛

var indexOf = function(search, target){

for(var k = 0; k < search.length; k++){

if(search[k] = target[0]){

var found = true;

for(var j = 0; j < target.length; j++){

found = found & (search[k + j] == target[j]);

}

if(found){

return k;

}

}

}

return -1;

}

console.log(indexOf('this works','works'));

console.log(indexOf('AAAB','AAB'));

｝｝

KMP (easy if you know that)

```
vector<int> BuildPrefixFunction(const string& s) {
vector<int> result(s.length(), 0);
for (int i = 1; i < s.length(); ++i) {
int j = result[i-1];
while (j && s[i] != s[j]) j = result[j-1];
if (s[i] == s[j]) ++j;
result[i] = j;
}
return result;
}
```

Z function (Google that)

But would prefer hash here. Polynomial hashes would work perfectly here.

KMP (easy if you know that)

```
vector<int> BuildPrefixFunction(const string& s) {
vector<int> result(s.length(), 0);
for (int i = 1; i < s.length(); ++i) {
int j = result[i-1];
while (j && s[i] != s[j]) j = result[j-1];
if (s[i] == s[j]) ++j;
result[i] = j;
}
return result;
}
```

Z function (Google that)

But would prefer hash here. Polynomial hashes would work perfectly here.

```
#include<stdio.h>
#include<string.h>
#define MAX 80
int find();
int main()
{
int n;
n=find();
if (n!=0)
printf("\n First occurence of first string is at %d position of second string", n);
else
printf("\n Not found!");
return(0);
}
int find()
{
char str2[MAX],str1[MAX],*str3;
int len2,i,n=0;
printf("Enter the first string:\n");
gets(str1);
printf("Enter the second string:\n");
gets(str2);
len2=strlen(str2);
for (i=0;i<len2;i++)
{
if (str2[i]==str1[0])
{
str3=strstr(str2,str1);
printf("\n Found...:\t %s", str3);
n=i;
break;
}
else
n=0;
}
return (n);
}
```

int indexOf(String a, String b) {

if (a == null || a.isEmpty() || b == null || b.isEmpty())

return -1;

if (a.length() > b.length())

return -1;

int max = b.length() - a.length() + 1;

int bx = 0;

while (bx < max) {

if (a.charAt(0) != b.charAt(bx)) {

bx++;

while (bx< max && a.charAt(0) != b.charAt(bx)) {

bx++;

}

} else {

boolean found = true;

for (int i = 1; i < a.length() && bx + i < b.length(); i++) {

if (a.charAt(i) != b.charAt(bx + i)) {

found = false;

break;

}

}

if (found)

return bx;

bx++;

}

}

return -1;

}

```
int indexOf(String a, String b) {
if (a == null || a.isEmpty() || b == null || b.isEmpty())
return -1;
if (a.length() > b.length())
return -1;
int max = b.length() - a.length() + 1;
int bx = 0;
while (bx < max) {
if (a.charAt(0) != b.charAt(bx)) {
bx++;
while (bx< max && a.charAt(0) != b.charAt(bx)) {
bx++;
}
} else {
boolean found = true;
for (int i = 1; i < a.length() && bx + i < b.length(); i++) {
if (a.charAt(i) != b.charAt(bx + i)) {
found = false;
break;
}
}
if (found)
return bx;
bx++;
}
}
return -1;
}
```

he easy C++ way to do this is to use std::string::find:

std::string s = "apple";

std::string sub = "ple";

auto index = s.find(sub); //std::string::npos if not found

The way for C would be strstr:

const char *s = "apple";

const char *sub = "ple";

const char *pos = strstr(s, sub); //NULL if not found

Worst case Complexity : O(n)

```
public class Practice65 {
public static void main(String args[]){
String str1 = "abcdefcde";
String str2 = "de";
int j=0,i=0;
while(i<str1.length()){
if(str2.charAt(j) == str1.charAt(i)){
j++;
i++;
if(j == str2.length()){
System.out.println(i - str2.length());
break;
}
}else{
j=0;
i++;
}
}
}
}
```

Yeah, I forgot to consider that case. The following code will work for upper case as well.

```
public class Practice65 {
public static void main(String args[]){
String str1 = "AAAABBAABBAAABAB";
String str2 = "AABBAAA";
int j=0,i=0;
while(i<str1.length()){
if(str2.charAt(j) == str1.charAt(i)){
j++;
i++;
if(j == str2.length()){
System.out.println(i - str2.length());
break;
}
}else{
i = i - j; // Add this piece of code.
j=0;
i++;
}
}
}
}
```

Once you add that line, the complexity becomes O(mn) with m being the length of the 2nd string. Basically, at i-th position of str1, you check

`if (str1.charAt(i+j) == str2.charAt(j))`

for j=0 to str2.length()-1. If it passes, you get the answer. But if it fails, you move to the (i+1)-position and start all over again.

Haha. Can you write the code? You have about 20 min for that (time limit for a such question).

It is easier to code Rabin Karp with the same average complexity. It could be done for such time constraints.

- kirotawa January 24, 2014