## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

Strange that none so far mentioned about KMP algorithm. This is a classic case of Knuth-Morris-Pratt algorithm. Check wiki for more details.
Rabin-Karp is too heavy for this.

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

KMP maintains a table. I think Rabin-Karp or KMP both would be expected answers, but people on this forum think that "in-place" means no additional memory is allocated. I don't believe that's true. I think 'in-place' means that don't copy the string in other places such as arrays or suffix trees.
I don't know what you mean by Rabin-Karp is heavy. It only calculates the hash for the pattern, and then its rolling hash O(1) operation when inside the loop. On average should perform O(length of text)

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

2nd string is the sub-string of 1st string. For getting the position from where 2nd string start.
in java
here i am taking 1st string as a and 2nd string as b.

a=o.readLine();a=a.trin(); // taking input of 1st string
b=o.readLine();b=b.trim(); // taking input of 2nd string
String c=b.substring(0,1); // find the first word of 2nd strig
Int i=a.indexOf('c'); // finding the index from where 2nd string start in the 1st string

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

Try Rabin-Karp

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

we have to do this in-place. So Rabin-Karp cant be applied

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

what do u mean by inplace , lets say we apply a solution to pointer to the strings . is it ok then ?

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

inplace menas that no extra memory should be allocated for doing the substring comparison. For Rabin-Karp, memory would be required for hashing purpose. Hence, it cant work in this case.

One approach might be to use the naive approach for this. But I am sure the interviewer might be looking for something smarter.

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

we can do a back search algorithm
If the character that is
compared with the rightmost pattern symbol does not occur in the pattern at all, then the pattern can be shifted by m positions behind this
text symbol.

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

Rabin-Karp doesn't require a full hash table for the string. It operates only with current and prev hash values and with a reference hash value: 3 variables in total = O(1) .

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

int findPosition(String S1, String S2)
{
int i=0;
int j;
for(j=0;j< S1.length();j++){

char tempchar= S2.charAt(i);
if(tempchar==S1.charAt(j)){
i++;
if(i==S2.length()){
break;
}
}
else { i=0; }

}

if(i==S2.length()){
j=j-S2.length()+1;
}
else j=0;
return j;
}

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

#include<stdio.h>
#include<string.h>
int main()
{
char str1[10000];
char str2[10000];
int arr[100000];
int i,j,k1,k2,temp=0,position,k,t=0;
scanf("%s",str1);
scanf("%s",str2);
k1=strlen(str1);
k2=strlen(str2);
for(i=0;i<k1;i++)
{
temp=0;
if(str1[i]==str2[0])
{
temp=temp+1;
position=i;
k=i+1;
for(j=1;j<k2;j++)
{
if(str1[k]==str2[j]){
temp=temp+1;
k=k+1;
}
else{
break;
}

}
}
if(temp==k2)
{
arr[t]=position+1;

t=t+1;
}
}
for(i=0;i<t;i++)
{
printf("%d ",arr[i]);
}
return 0;
}

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

/*
1. Start from the end of both strings
2. compare last element of str2 with str1
- if matches compare next element from last and so on
-if str2 start is reached return Str1 current position
- if doesnt match start comparing str2's last element and Str1 current element
*/

bool CheckSubString(char * Str1, char * Str2, int len1, int len2)
{
int last1 = len1 - 1;
int last2 = len2 - 1;
int i = last1;
int j = last2;

if(len1 < len2)
{
return -1;
}

while(i >= 0 && j >= 0)
{
if(Str1[i] == Str2[j])
{
i--;
j--;
continue;
}
else
{
j = last2;
i--;
}

}
if(j == -1)
{
return (i+1);
}

return -1;
}

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

Why are you returning bool? It should be int.

Additionally, you should start searching on the left, not on the right.

i.e. for
string s1 = "abcdefgefg";
string s2 = "efg";

Best.

Edit: improved your code a little :)

#include <iostream>
#include <string>

using namespace std;

int CheckSubString( const char * Str1, const char * Str2, int len1, int len2)
{
int iter1 = 0;
int iter2 = 0;
int i = iter1;
int j = iter2;

if(len1 < len2)
{
return -1;
}

while( i < len1 && j < len2 )
{
if( Str1[i] == Str2[j] )
{
i++;
j++;
}
else
{
j = 0;
i++;
}
}

if(j >= len2 )
{
return i - len2;
}

return -1;
}

int main()
{
string s1 = "abcdefnefg";
string s2 = "efg";

printf( "%d", CheckSubString( s1.c_str( ), s2.c_str( ), s1.length( ), s2.length( ) ) );

getchar();

return 0;

}

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

int StringMatch(string& A, string& B)
{

for(int i=0; i< A.size(); i++)
{
int j=0;

if(A[i] == B[0])
for(; j<B.size(); j++)
{
if((j+i) >= A.size())
break;
if(A[j+i] != B[j])
break;
}
if(j == B.size())
return i;
i += j;
}
return -1;
}

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

sort the given array
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
swap(a[j],a[i]);
print(a);
swap(a[j],a[i])
}
please tell me i m doing it right or wrong

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

sort the given array
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
swap(a[j],a[i]);
print(a);
swap(a[j],a[i])
}
please tell me i m doing it right or wrong

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

sort the given array
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
swap(a[j],a[i]);
print(a);
swap(a[j],a[i])
}
please tell me i m doing it right or wrong

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

rabin karp
or
boyer moore
or

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

if iam taking string objects cann't i use find function in <string>
str.find(str1)

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

I can not tell the exact algorithm, but I am sure that if you build a suffix tree, which can be done on linear time, then checking if the second string is in the tree is also linear and as far as I remember it was very easy to get the node of the tree which points to the start of the string.

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

Doesn't work if the two strings are identical.
Using the name ptr for an integer is poor style.

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.