|
Given a stream of text eg you can read 1 char at a time.....
Microsoft Interview Questions and Answers
(Continued from previous question...)
39. Given a stream of text eg you can read 1 char at a time.....
Question:
Given a stream of text eg you can read 1 char at a time, write fn that will return true if you can find a string str in the stream before the stream runs out
What if the string you are looking for is abc
And the stream is aaabababcab
I gave a solution using a stringbuilder ( like a circular array) but he didn’t like it. He wanted a solution that doesn’t require space equal to the string you are looking for
maybe an answer:
In most of the cases of "stream of text" type of problem, the interviewer is asking if you can create a DFA/NFA for the pattern. All you have to do is create a state machine, whose final state is 'c' and on transition from B (which can be reached using transition from B).
State1 --transition--> State2
[start]--a-->[A]
[A]--b-->[B]
--anything else-->[start]
[B]--c-->[terminal]
[B]--a-->[A]
[B]--c-->[terminal]
--anything else -->[start]
[terminal]--anything-->[terminal]
maybe an answer2:
public static void main(String []args)
{
String Pattern = "aaabbddddbadfbbbassb";
String strMatch = "aaa";
int strLength = strMatch.length();
int final_count=3;
int count=0,j=0,i=0;
while(true)
{
if(strMatch.charAt(j++)==Pattern.charAt(i))
{
count+=1;
if(count==strLength)
{
System.out.println("String found at index " + (i-1));
return;
}
i++;
}
else
{
j=0;
i++;
count=0;
continue;
}
}
}
Here disregard int final_count=3; In addition to that instead of considering we have been given String Pattern = "aaabbddddbadfbbbassb";...We can assume that we are getting this string from the console or some file etc.
maybe an answer3:
//My code read only one char at a time from the stream and doesnot require any extra
//storage. I only store the pattern to search for.
//The main idea depends on transtion states and taking into account several
//different possible cases
static void Main()
{
Console.Write("Pattern: ");
string pattern = Console.ReadLine();
Console.WriteLine("Input your stream ended with Enter key");
char ch;
int patternIndex = 0;
int currentState = 0;
int stopState;
while ((ch = (char)Console.Read()) != '\r' && patternIndex !=
pattern.Length)
{
if (pattern[patternIndex] == ch)
patternIndex++;
else
{
stopState = patternIndex;
currentState++;
patternIndex = 0;
while (currentState <. stopState)
{
int tempState = currentState;
while (pattern[tempState] == pattern[patternIndex] &&
tempState < stopState)
{
tempState++;
patternIndex++;
}
if (tempState == stopState && ch == pattern[patternIndex])
{
patternIndex++;
currentState--;
break;
}
else
{
currentState++;
patternIndex = 0;
}
}
if (currentState == stopState)
{
currentState = 0;
if (ch == pattern[patternIndex])
{
patternIndex++;
currentState--;
}
}
}
}
if (patternIndex == pattern.Length)
Console.WriteLine("Found....!!!!");
else
Console.WriteLine("NOT Found....!!!!");
}
(Continued on next question...)
Other Interview Questions
| 