Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
#include<iostream>
using namespace std;
#include<string.h>
main()
{
char str[100];
cin>>str;
char c;
fflush(stdin);
c=getchar();
int i,len;
len=strlen(str);
i=0;
while(c!='\n')
{
if(c==str[i])
{
i++;
if(i==len)
{
cout<<"matched";
break;
}
}
else if(c==str[0])
{
i=1;
}
else
{
i=0;
}
c=getchar();
}
if(c=='\n')
cout<<"Did Not Match";
}
Make a finite automation from the string to be searched. Process each character from the stream and update the state of the automation. If at any time we are on the accepting state, declare the result. [ Cormen Chapter 32, Section 32.3]
We can't use Rabin-Karp as the question says we can't store the stream ( which I take it as we are not even allowed to store the string of size equal to the string to find. In Rabin-Karp, once we find the match, we need to verify whether it actually matches ).
Let len be the number of chars in str. Store the incoming characters of the stream in a queue of len elements. Every time you accept a new char from the stream, append the new character to the one end and dequeue a character from the opposite end. Check if the character sequence stored in the queue is equal to str. If so, then set a global bool variable to true.
The code is in C
Function returns 0 on failure and 1 on success
int match_str(char str[])
{
char ch,*temp=str;
int len,count=0;
for(len=0;str[len];len++);
while(scanf("%c",&ch))
{
if(ch=='\n')
break;
if(*temp!=ch && count)
{
temp=str;count=0;
}
if(*temp==ch)
{
temp++;count++;
}
if(count==len-1)
return 1;
}
return 0;
}
#include<iostream>
using namespace std;
#include<string.h>
main()
{
char str[100];
cin>>str;
char c;
fflush(stdin);
c=getchar();
int i,len;
len=strlen(str);
i=0;
while(c!='\n')
{
if(c==str[i])
{
i++;
if(i==len)
{
cout<<"matched";
break;
}
}
else if(c==str[0])
{
i=1;
}
else
{
i=0;
}
c=getchar();
}
if(c=='\n')
cout<<"Did Not Match";
}
you do 1 thing.first find the size of string str.then search that lenght @ 1 time .means read 1 character match that with the character in str.if same move forward else discard that character and move next.
boolean MatchString(Stream stream, String str)
{
boolean done= false;
int i = 0;
while(!done)
{
char c = stream.readNextChar();
if(str.charAt(i) == c )
{
if(i == (str.length-1))
{
return true;
}
i++;
}
else
{
i = 0;
}
}
}
@anonymous: a small mistake in your algo..
boolean MatchString(Stream stream, String str)
{
boolean done= false;
int i = 0;
while(!done)
{
char c = stream.readNextChar();
if(str.charAt(i) == c )
{
if(i == (str.length-1))
{
return true;
}
i++;
}
else if(c == str.charAt(0))
i=1;
else
{
i = 0;
}
}
}
@leet and @anonymous: when the loop ends???
can i write
if( c == '\0')
return false;
if i am wrong what is the condition for the loop to terminate if the stream is stopped..
@cobra and leet: I guess its perfect now and only possible improvement could be spawning a new thread that invokes this function MatchString after reading each character in the stream. The complexity could go very high as a result of spawning of the multiple threads.
I guess we cant do any thing about it. Only possible way to avoid it is use threads for each input. from the stream
if stream is "abaaab" and we are looking for "aab", the above matchString() does not seem to work. Please correct me if i am wrong. I tried in eclipse, and it failed...
@VRAM: ya man.. it wont work.. u have to use KMP string matching algorithm.. for the solution.. see my comment at the top
@VRAM you might have overlooked else if(c==charAt(0)) step..
this code works for your string aab also..pls check
use KMP string Matching.. for solution: ideone.com/t2nPA
- cobra August 06, 2012