Flipkart Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
if (regexp[0] == '^')
return matchhere(regexp+1, text);
do { /* must look even if string is empty */
if (matchhere(regexp, text))
return 1;
} while (*text++ != '\0');
return 0;
}
/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
if (regexp[0] == '\0')
return 1;
if (regexp[1] == '*')
return matchstar(regexp[0], regexp+2, text);
if (regexp[0] == '$' && regexp[1] == '\0')
return *text == '\0';
if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
return matchhere(regexp+1, text+1);
return 0;
}
/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
do { /* a * matches zero or more instances */
if (matchhere(regexp, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
Here iw working python code
def check_regex(reg, exp):
if reg[0] == '^':
reg = reg[1:]
elif reg[-1] == '$':
reg = reg[:-1]
i = 0
j = 0
while i<len(exp):
if reg[j] == '.':
i += 1
elif reg[j] == '*':
while(exp[i-1] == exp[i]):
i += 1
elif exp[i] == reg[j]:
i += 1
else:
return False
j += 1
return True
#include<stdio.h>
#include<string.h>
int expressionvalidator(char *,char *,int);
int main()
{
char exp[100],tstcse[100];
int s;
printf("Enter the expression\n");
gets(exp);
printf("test case\n");
gets(tstcse);
//char exp1='o',tstcse1='p';
//printf("%d",strlen(exp));
s=expressionvalidator(exp,tstcse,strlen(exp));
switch(s)
{
case 1: printf("true");
break;
case 0: printf("false");
}
}
int expressionvalidator(char *exp,char *tstcse,int length)
{
char *ptr,*tpt;int i;
//printf("%c and %c",*exp,*tstcse);
if(*exp == '^')
{
exp++;
length--;
}
if(*exp == '*' || *exp == '$')
return 0;
while((*exp) != '\0')
{
for(i=0;i<length;i++)
{
//printf("Equal1");
if((*exp) == (*tstcse))
{
ptr=exp;
exp++;
tstcse++;
//printf("Equal");
}
else if( (*exp) == '*')
{
if(*ptr == *tstcse || *ptr == '.')
{
if(*ptr == *tstcse)
{
while(*ptr == *tstcse)
{
tstcse++;
}
ptr = exp;
exp++;
}
else
{
while(*tpt == *tstcse)
{
tstcse++;
}
ptr = exp;
exp++;
}
}
else
{
exp++;
if(*exp == *tstcse)
{
ptr=exp;
exp++;
tstcse++;
}
else
{
return 0;
}
}
}
else if( (*exp) == '.')
{
tpt = tstcse;
ptr=exp;
exp++;
tstcse++;
}
else if(*exp == '$')
{
return 1;
}
else
{
return 0;
}
}
}
return 1;
}
Workable java code with comments -
public class StringMatchingRegex {
public static void main(String args[]) {
String tests[][] = { {"ab", "ab" },
{"a*b" , "aaaaaab"},
{"a*b*c*", "abc"},
{"a*b*c" , "aaabccc"},
{"^abc*b", "abccccb"},
{"^abc*b", "abbccccb"},
{"^abcd$", "abcd"},
{"^abc*abc$" , "abcabc"},
{"^abc.abc$", "abczabc"},
{"^ab..*abc$", "abyxxxxabc"}
};
for (int i = 0; i < tests.length; i++) {
boolean yes = matches(tests[i][0] , tests[i][1]);
System.out.println(tests[i][0] +" "+ tests[i][1] + " = " + yes);
}
}
private static boolean matches(String regex, String string) {
if (regex == null || string == null) {
return false;
}
boolean result = true;
int k = 0;
for (int i = 0; i < regex.length(); i++) {
char c = regex.charAt(i);
if (isAlpha(regex.charAt(i))) {
if (k < string.length() && string.charAt(k++) == regex.charAt(i)) {
continue;
} else {
result = false;
break;
}
} else {
k = handle(string, k, c);
if (k == -1 ) {
result = false;
break;
}
}
}
if (k < string.length()) {
//there is still unmatched string
result = false;
}
return result;
}
private static boolean isAlpha(char c) {
return Character.isLetter(c);
}
private static int handle(String string, int i, char c) {
switch (c) {
case '.':
//match a character
if (i >= string.length()) {
return -1;
}
return ++i;
case '?' :
//match 0 or 1 character
if (i < string.length() && string.charAt(i) == string.charAt(i-1)) {
return ++i;
} else {
return i;
}
case '+':
//one or more
int count = 0;
char prev = string.charAt(i-1);
while (i < string.length() && string.charAt(i) == prev ) {
count++; i++;
}
if (count >= 1) {
return i;
} else {
return -1;
}
case '*':
//match 0 or more characters
if (i >= string.length()) {
return i;
}
count = 0;
prev = string.charAt(i-1);
while (i < string.length() && string.charAt(i) == prev ) {
count++; i++;
}
if (count >= 0) {
return i;
} else {
return -1;
}
case '^':
if (i!=0) {
throw new IllegalArgumentException("Invalid regex");
}
return i++;
case '$':
if (i == string.length()) {
return ++i;
} else {
return -1;
}
}
//some unknown character
return -1;
}
}
in :
11
ab ab
a*b aaaaaab
a*b*c* abc
a*b*c aaabccc
^abc*b abccccb
^abc*b abbccccb
^abcd$ abcd
^abc*abc$ abcabc
^abc.abc$ abczabc
^ab..*abc$ abyxxxxabc
^abc*b abbccccb
- Anonymous August 19, 2014#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <ctype.h> using namespace std; int main() { //freopen("A-large-practice.in", "r", stdin); //freopen("A-small-practice.in", "r", stdin); freopen("in", "r", stdin); freopen("out", "w", stdout); int n; scanf("%d", &n); while(n--) { char regex[100], expression[100], c, temp; scanf("%s", regex); scanf("%s", expression); int i =0 ,j = 0,flag = 1; while(regex[i] != '\0' && flag == 1) { c = regex[i]; switch(c) { case '^': i += 1; break; case '$': i += 1; break; case '*': temp = regex[i-1]; if(temp == '.') temp = expression[j-1]; while(temp == expression[j]) j += 1; i += 1; break; case '.': if(isalpha(expression[j])) { j += 1; i += 1; } else flag = 0; break; default: if(regex[i] == expression[j]) { i += 1; j += 1; } else flag = 0; } } if(flag == 0) printf("false\n"); else if(regex[i] == '\0' ^ expression[j] == '\0') printf("false\n"); else printf("true\n"); } return 0; }