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.

- arkadi.kagan October 11, 2014 | Flag Reply
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;
	}
}

- R@M3$H.N October 13, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More