## Facebook Interview Question for Software Engineer / Developers

Country: United States

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

use recursion. When a * is found and it is not the ending char in the pattern, find each occurrence of the next non-* char of the pattern in the text, call recursion for the substring in the text starting from each occurrence. Return true if any of the recursion is true.

``````bool mainfunc(char *t, int tlen, char *p, int plen)
{
return f(t, 0, tlen-1, p, 0, plen-1);
}

// recursion function
bool f(char *t, int tst, int tend, char *p, int pst, int pend)
{
if(tst>tend || pst>pend)
return false;

int ti, pi; //ti:index of t; pi:index of p
ti=tst;
pi=pst;

bool foundStar = false; // differentiate match chars w/wo *

while(ti<=tend && pi<=pend)
{
while(p[pi]=='*')
{
pi++;
foundStar=true;
}

if(pi>pend)
return true; // the last char is * in pattern

if(foundStar)
{
// match with each occurrence of p[next], return if anyone is true
for(int i=ti;i<=tend;++i)
{
if(t[i]==p[pi] && f(t,i+1,tend,p,pi+1,pend)==true)
{
return true;
}
}

return false; //none of them return true.
}

if(t[ti]!=p[pi])
return false;

ti++;
pi++;
}

if(ti<=tend || pi<=pend)
return false;

return true;
}``````

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

here is the code. It checks if the second string is a pattern in a first string. for instance try:
./a.out "This is the string " "is*is"
./a.out "This is the string d " "*is*is*dd"
./a.out "This is the string dd " "*is*is*dd"
./a.out "This is the string dd " "*is*is*dd**k"

the code:

``````#include <iostream>
using namespace std;

bool checkPattern(char *input, char *pattern) {
int inputIndex=0;
int patternIndex=0;
while(input[inputIndex] != '\0') {
if(pattern[patternIndex] == '\0') return true;
else if(pattern[patternIndex] == '*') patternIndex++;
else if(pattern[patternIndex] == input[inputIndex] ) {inputIndex++; patternIndex++;}
else if(pattern[patternIndex] != input[inputIndex] ) inputIndex++;
}
return false;
};

main(int argc,char * argv[])
{
cout << "string: \'" <<  argv[1] << "\'" << endl << "pattern: \'" << argv[2] << "\'" << endl;
checkPattern(argv[1],argv[2]) ? cout << "yay" : cout << "nay";
cout << endl;
}``````

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

I don't think the code is correct:

"This is the string " "is*is" should not be a match, but your program returned "yay"

Moreover, whether inputIndex can keep increasing definitely depends on whether the previous pattern character is a wildcard *

Also, I don't think you took care of the case when the pattern runs out but input still has characters left, which should not be a match, e.g., "xyzxyz" should not be a match for "*y*y"

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

use kmp as follows:
1. cut down the head and tail which is not '*' from the pattern, and match the head and tail with the text. If match, cut down the text head and tail and go on to 2; returns false otherwise.
2. split the remaining pattern by * and build the kmp for each part, then use them to match the text one by one.
in the above case, '*dad' matches 'cdad', then '*ba' matches 'aba', the last '*' is for the tailing 'c'. done.

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

//Kmp algorithm with some modification works fine

#include<iostream>
#include<string>
using namespace std;
int array[100];
void precompute(string original,string matched)
{
int k=0;
array[0]=0;
for(int q=1;q<matched.length();q++)
{
while(k>0&&(matched[k+1-1]!=matched[q])&&matched[k+1-1]!='*')
{
k=array[k-1];
//cout<<k<<"hii"<<endl;
}
if(matched[k+1-1]==matched[q]||matched[k+1-1]=='*')
k=k+1;
array[q]=k;
// cout<<array[q]<<endl;
}
}
int main()
{
//Kmp-algorithm
string original,matched;
cin>>original;
cin>>matched;
int q=0;
precompute(original,matched);
for(int i=0;i<original.length();i++)
{
while(q>0&&(matched[q+1-1]!=original[i]&&matched[q+1-1]!='*'))
q=array[q-1];
if(matched[q+1-1]==original[i]||matched[q+1-1]=='*')
q=q+1;
if(q==matched.length())
{
cout<<i+2-matched.length()<<endl;
q=array[q-1];
}

}
system("pause");
return 0;

}

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

Please correct me if I was wrong:
it is true that an input string matches the given pattern once satisfying:
1) pattern length equals with input string's length;
2) fixed characters in pattern match the ones in the same positions of input string

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

Try it out at: ideone.com/eG3sQ

``````bool Matches(const string& str, const string& pattern) {
int pos = 0;
int str_len = str.size();
int pattern_len = pattern.size();
bool saw_wildcard = false;
for (int i = 0; i < pattern_len; ++i) {
if (pattern[i] == '*') {
saw_wildcard = true;
continue;
}

if (saw_wildcard) {
while (pos < str_len && str[pos] != pattern[i])
pos++;
if (pos == str_len)
return false;
else
pos++;
} else {
if (str[pos] != pattern[i])
return false;
else
pos++;
}

saw_wildcard = false;
}

// if last char in pattern is not a wildcard, then extra char in the input should not match
if (!saw_wildcard && pos < str_len)
return false;

return true;
}``````

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

#include<iostream>
#include<string>
using namespace std;

struct node
{
char a;
node *l;
int flag;
}*start;

bool matchReg(node *q,int i);

string t,p;
int n,m;

int main()
{
start=NULL;
node *temp,*q;

cin>>t;
cin>>p;

n=t.length();
m=p.length();

int i;
i=0;

if(t[i]=='*')
i++;

while(i<n-1)
{
if(t[i+1]=='*' && t[i]!='*')
{
if(start==NULL)
{
start=new node;
start->a=t[i];
start->l=NULL;
start->flag=1;
temp=start;
}
else
{
q=new node;
q->a=t[i];
q->l=NULL;
q->flag=1;
temp->l=q;
temp=q;
}
}
else if(t[i]!='*')
{
if(start==NULL)
{
start=new node;
start->a=t[i];
start->l=NULL;
start->flag=0;
temp=start;
}
else
{
q=new node;
q->a=t[i];
q->l=NULL;
q->flag=0;
temp->l=q;
temp=q;
}
}
i++;

}

if(t[i]!='*')
{
if(start==NULL)
{
start=new node;
start->a=t[i];
start->l=NULL;
start->flag=0;
temp=start;
}
else
{
q=new node;
q->a=t[i];
q->l=NULL;
q->flag=0;
temp->l=q;
temp=q;
}
}

if(matchReg(start,0))
cout<<"Accepted";
else
cout<<"Rejected";

}

bool matchReg(node *q,int i)
{
if(q==NULL && i==m)
return true;
else if(q==NULL && i!=m)
return false;
else if(q->l==NULL && q->flag==1 && i==m)
return true;
else if(q!=NULL && i==m)
return false;
else if(q->a!=p[i] && q->flag==0)
return false;
else if(q->a==p[i] && q->flag==0)
return matchReg(q->l,i+1);
else
{
bool b1=matchReg(q->l,i+1);
bool b2=matchReg(q,i+1);
bool b3=matchReg(q->l,i);

return (b1||b2||b3);
}

}

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

Another recursion using different function signature.

``````bool f(char* s, char* p)
{
if(*s=='\0' && *p=='\0')
return true;
if(*s=='\0' && *p=='*')
return f(s, p+1);
if(*s=='\0')
return false;

bool foundStar = false;
char* cur = p;

//handle multiple stars in a row.
while(*cur == '*')
{
cur++;
foundStar = true;
}

//if ending with *, return true.
if(*cur == '\0')
return true;

if(foundStar)
{
return f(s+1, cur-1) || f(s, cur) || f(s+1, cur);
}
else
{
if(*cur==*s)
return f(s+1, cur+1);
else
return false;
}
}``````

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

kmp pattern matching algorithm can be used

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

ppl who heard about advanced algorithms but have no idea when to use dem

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

agree :)

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.