## Amazon Interview Question for Testing / Quality Assurances

Team: Kindle
Country: India
Interview Type: Written Test

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

The simplest way is to for every character check the following n characters (where n is the length of the substring) to see whether they equal. This approach is O(N_String * N_Substring).

A better approach is to use the Knuth-Morris-Pratt algorithm en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm which achieves O(N_String) performance but it's probably too involved for an interview question. But knowing it exists would probably be worth some brownie points.

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

There are lots of string search algorithms.

1. Brute force ( Moving by 1 till end )
2. Rabin Karp ( Use rollover hashing )
3. Horspool ( Shifting to last matched item )
4. KMP ( Create DFA and use it for searching )

You can use any of the above four. I feel KMP is faster then others when string contains repeated characters.

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

There is the famous KMP Algorithm for this

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

int substring(char *str,char *substr)
{
int i,j=0,len,len2;
len=strlen(substr);
len2=strlen(str);
for(i=0;i<len2-len;i++)
{
if(*(str+i)==*(substr+j))
{
j++;
}
if(j==len)
return(0);
}
if(j==len)
return(0);
else
return(1);
}

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

I wrote in shell script , answer accepted.

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

Java-

Boolean SubString(String str,String str1){
int j=0
for (int i=0;i<str.lenght();i++){

if(str.charAt(i)==str1.charAt(j)){

j++;
}
else{
j=0;
}
if(j==str1.length()){
return True;
}
}
return False;
}

Please comment in case of any error

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

Will fail in following scenario:
txt[] = "AAAAABAA"
pattern[] = "AABA"

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

``````int main()
{
char string[] = "my name is megharaj I an from india";
char *stringp = string;
char sub[] = "an";
int length = strlen(sub) -1;
char *temp;
while(*stringp != '\0') {
temp = sub;
length = 2;
while((stringp != '\0') && (*stringp == *temp) && length > 0) {
stringp++;
temp++;
length--;
if(length == 0) {
printf("substring found\n");
return 0;
}
}
stringp++;
}
return 0;
}``````

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

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

int main(){
char *s= malloc(50);
char *sub=malloc(5);
printf("Enter a string :\n");
fgets(s,40,stdin);
printf("Enter the sub string: \n");
fgets(sub,5,stdin);

char *temp=sub;
int count=0;

while(*s != '\0'){
if(*sub==*s && sub != '\0'){
count++;
sub++;
s++;
}
else if(count >strlen(temp) && *sub != *s && sub != '\0'){
count--;
sub--;
}
else{
s++;
}
}

if(count==strlen(temp)){
printf("Match found\n");
}
else{
printf("No match found\n");
}

return 0;
}``````

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

You may also want to free up the memory after all the operations. Forgot to do that.

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

public boolean checkSubstring(String subStr, String str)
{
int l=subStr.length();
int j=str.length();
for(int i=0;i<(j-l+1);i++)
{
String s=str.subString(i,i+l);
if(s.equals(subStr))
return true;
}
return false;
}

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

You should avoid to use readymade APIs available. Thinking in point of interviewer, he is expecting you to implement that substr API in java.

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

While your interviewer is probably looking for you to code this up without using any library at all, you'll get a lot of credit with more senior interviewers if you mention that there are pre-existing methods for this in the standard libraries for whatever language you are working in. In real life, if you don't use a regular expression match for this problem, you're being kind of thick. The last thing I want on the job is for developers to re-implement the Knuth algorithm for the 100th time.

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.