## Amazon Interview Question for Software Engineer / Developers

Team: Chennei
Country: India
Interview Type: Written Test

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

``````static bool regex(const char *expr, const char *seq)
{
if (expr[0] == 0)
return seq[0] == 0;
if (expr[1] == '*')
{
if (regex(expr + 2, seq))
return true;
for (int j = 0; seq[j] == expr[0]; j++)
{
if (regex(expr + 2, seq + j + 1))
return true;
}
return false;
}
if (expr[0] == seq[0])
{
if (expr[1] == '+')
{
for (int j = 0; seq[j] == expr[0]; j++)
{
if (regex(expr + 2, seq + j + 1))
return true;
}
return false;
}
return regex(expr + 1, seq + 1);
}
return false;
}``````

Than you have few months of work until you really give up and start over :)

Actually, I'd rather build the expression tree first. With expression tree you handle "*", "+", "[]", "()", etc. without redesigning the main loop over and over with each new supported syntax.

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

For simplicity i will consider the following, later can be extended for all:

* --- Matches 0 or more of the preceding char
. --- Matches any single char.

``````bool matchFirst(const char *str, const char *ptrn){
return ( (*ptrn == *str) ||
(*ptrn == '.' && *str != '\0')
);
}

bool isRegex(const char *str, const char *ptrn) {
//If the Pattern reaches end
if (*ptrn == '\0')
return *str == '\0';

//Case-1: If the Pattern's second char is not *
if (*(ptrn + 1) != '*') {
//If the first char of pattern is "." or first char of pattern == the first i char
//of string, continue to match the left part
if(!matchFirst(str,ptrn))
return false;
return isRegex(str + 1, ptrn + 1);
}
//Case-2: If the Pattern second char is *
else {
//If the first char of pattern is not ".", the first char of pattern and string
//should be the same.
//Else continue to match the rest
if(isRegex(str, ptrn + 2))
return true;
while ( matchFirst(str,ptrn) )
if (isRegex(++str, ptrn + 2))
return true;
}
}``````

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.