Amazon Interview Question
Testing / Quality AssurancesTeam: Kindle
Country: India
Interview Type: Written Test
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.
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
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++;
}
printf("substring not found\n");
return 0;
}
#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;
}
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;
}
You should avoid to use readymade APIs available. Thinking in point of interviewer, he is expecting you to implement that substr API in java.
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.
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).
- Anonymous April 12, 2013A 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.