Microsoft Interview Question for Software Engineer / Developers


Team: STC
Country: China
Interview Type: Phone Interview




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

Here is a generalization of this problem:

basicalgos.blogspot.com/2012/03/10-regular-expression-matching.html

- Andy April 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks, I just give the same idea.However ,the interview seems to have a better idea.So I wonder whether there is a better idea to solve this problem.

- Red Lv April 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

#/usr/bin/python

def match(string, pattern):
    if len(pattern) == 0 and len(string) == 0:
        return True

    if (len(pattern) == 0 and len(string) > 0) or (len(pattern) > 0 and len(string) == 0):
        return False

    if pattern[0] == "*":
        return match(string[1:], pattern[1:]) or match(string[1:], pattern)
    elif pattern[0] == string[0]:
        return match(string[1:], pattern[1:])
    else:
        return False

print match("abracadabra", "ab*ca*br*")

- texens September 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isMatchGeneral(const char *s, const char *p, int slen, int plen)
{
    if (s == NULL && p == NULL) return true;
    if (s == NULL || p == NULL) return false;
    
	if (plen == 0) return true;
	if (*p == '*') return isMatchGeneral(s, p+1, 0, plen-1);
	if (slen == 0) return false;
	
	int i=0;
	while (i < slen)
	{
		int j=0;
		while (s[i] != p[j])
		{
			i++;
			if (i == slen) return false;
		}
		int reserve = i;
		while (s[++i] == p[++j])
		{
			if (j==plen) return true;
			if (i==slen) return false;
		}
		if (j == plen) return true;
		if (p[j] == '*') return isMatchGeneral(s+i, p+j+1, slen-i, plen-j-1);
		if (i == slen) return false;

		i = reserve + 1;
	}

	return false;
}


bool isMatch(const char *s, const char *p, int slen, int plen) {
    if (s == NULL && p == NULL) return true;
    if (s == NULL || p == NULL) return false;
    
	if (slen == 0 && plen == 0) return true;
	if (slen == 0) 
	{
		if (*p == '*') return isMatch(s, p+1, 0, plen-1);
		else return false;
	}

	if (*p != '*')
	{
		if (*s != *p) return false;
		else return isMatch(s+1, p+1, slen-1, plen-1);
	}

	if (p[plen-1] != '*')
	{
		if (s[slen-1] != p[plen-1]) return false;
		else return isMatch(s, p, slen-1, plen-1);
	}

	return isMatchGeneral(s, p+1, slen, plen-2);
}

int _tmain(int argc, _TCHAR* argv[])
{
	char * s = "aaaabaaaaac";
	char * p = "a*ab*ba**c";
	cout<<isMatch(s, p, strlen(s), strlen(p))<<endl;


	char j;
	cin>>j;
	return 0;
}

- sp April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int match(const char *pattern, const char *string)
{
   register char c;

   while(1){
      switch(c = *pattern++)
      {
         case '*':   
            c = *pattern;   
            while(*string){
               if(1 == match(pattern, string))
                  return 1;
               ++string;
            }
         break;
         case '\0':
            return !*string ? 1 : 0;
            break;
         default:
            if(c != *string++)
               return 0;
         break;
      }
   }
}

- Nit May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int match(const char *pattern, const char *string)
{
register char c;

while(1){
switch(c = *pattern++)
{
case '*':
c = *pattern;
while(*string){
if(1 == match(pattern, string))
return 1;
++string;
}
break;
case '\0':
return !*string ? 1 : 0;
break;
default:
if(c != *string++)
return 0;
break;
}
}
}

- Anonymous May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;


bool checkForMatch(const char* str, const char* pattern){

if(str == NULL && pattern == NULL){
printf("both pattern and string are null\n");
return true;
}

if(str == NULL && pattern != NULL){
printf("Pattern is not null but string is null\n");
return false;
}

if (*pattern == '*'){
printf("Pattern is starting with *\n");
return false;
}

if (pattern == NULL && str != NULL){
printf("Pattern is null but string is not null\n");
return false;
}

char* patternStart = (char*) pattern;
char* patternBegin = (char*) pattern;
int index = 0;
int count = 0, i=0;
char* subStr = NULL;
int origLen = strlen(str);

while(*patternStart){
count = 0;
i = 0;
while(*patternStart && *patternStart != '*'){
count++;
patternStart++;
}

subStr = (char*) malloc(sizeof(char) * (count + 1));
strncpy(subStr, patternBegin, count);
subStr[count] = '\0';

for(; i<count - 1; i++){
if(str[index] != subStr[i]){
return false;
}
index++;
}

while(str[index] == subStr[i]){
index++;
}

patternBegin = ++patternStart;
}

if(index < origLen){
return false;
}

return true;

}



int main(){
char* origStr = "aaabba";
char* regEx = "aa*bb*a";

bool isValid = false;

isValid = checkForMatch(origStr, regEx);

if(isValid){
printf("String matched the expression\n");
}
else{
printf("String didn't matched the expression\n");
}

system("pause");

return 0;
}

- Solution without recursion August 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry it won't work for aab and a*ab

- Anonymous August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now i have fixed it and here is the correct solution.
=====================================


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;


bool checkForMatch(const char* str, const char* pattern){

if(str == NULL && pattern == NULL){
printf("both pattern and string are null\n");
return true;
}

if(str == NULL && pattern != NULL){
printf("Pattern is not null but string is null\n");
return false;
}

if (*pattern == '*'){
printf("Pattern is starting with *\n");
return false;
}

if (pattern == NULL && str != NULL){
printf("Pattern is null but string is not null\n");
return false;
}

char* patternStart = (char*) pattern;
char* patternBegin = (char*) pattern;
int index = 0;
int count = 0, i=0;
char* subStr = NULL;
int origLen = strlen(str);

while(*patternStart){
count = 0;
i = 0;
while(*patternStart && *patternStart != '*'){
count++;
patternStart++;
}

subStr = (char*) malloc(sizeof(char) * (count + 1));
strncpy(subStr, patternBegin, count);
subStr[count] = '\0';

for(; i<count - 1; i++){
if(str[index] != subStr[i]){
return false;
}
index++;
}

while(str[index] == subStr[i]){
index++;
}

if(*(patternStart + 1) == subStr[i]){
++patternStart;
}

patternBegin = ++patternStart;
}

if(index < origLen){
return false;
}

return true;

}



int main(){
char* origStr = "aaa";
char* regEx = "a*a";

bool isValid = false;

isValid = checkForMatch(origStr, regEx);

if(isValid){
printf("String matched the expression\n");
}
else{
printf("String didn't matched the expression\n");
}

system("pause");

return 0;
}

- Anonymous August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reg_expression()
{
    string reg_exp;
    string test_str;
    
    cout<<"\nEnter the regular expression : ";
    cin>>reg_exp;
    
    bool *bFlag;
    int nSize = reg_exp.length();
    bFlag = new bool[nSize]();    
      
    cout<<"Enter the string u want 2 check: ";
    cin>>test_str;

    int i = 0;
    int j = 0;
    
       while(j != test_str.length())
       {
           if(reg_exp[i] == '*')
           {
               i++;
               continue;
           }
           if(reg_exp[i] == test_str[j])
           {
               bFlag[i] = true;
              j++;
           }
           else if(bFlag[i])
           {
              i++;
           }
           else
           {
               break; 
           }
       }

       cout<<"\nResult : ";
       if((j == test_str.length()) && (i == reg_exp.length() - 1))
       {
           cout<<" \""<<reg_exp<<"\" can generate string \""<<test_str<<"\".";
       }
       else
       {
            cout<<" \""<<reg_exp<<"\" cannot generate string \""<<test_str<<"\".";
       }

}}

- MehraD September 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

isMatching(char* pattern, char* string) {

char cur_match = *pattern;
char next = *(pattern+1);

if( next == '*') { //Multiple character matching a*
while( *string == cur_match)
string++;
pattern+=2;
}

else{ //Single Character match (Eg aa* here match only the first a)
if(*string != cur_match)
return false;
string++;
pattern++;
}
}

- Raghavendra October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# code for taking care of * and ?

public static bool PatternMatch(string text, string pattern)
        {
            // Validate input
            // can text contain regex characters??
            // this code doesn't take care or escaping regex character
            return PatternMatch(text, 0, pattern, 0);
        }

        private static bool PatternMatch(string text, int txtInd, string pattern, int patInd)
        {
            if (text.Length == txtInd && pattern.Length == patInd)
                return true;
            if (text.Length == txtInd || pattern.Length == patInd)
                return false;
            if ((text[txtInd] == pattern[patInd]) || (pattern[patInd] == '?'))
                return PatternMatch(text, txtInd+1, pattern, patInd+1);
            if (pattern[patInd] == '*')
                return PatternMatch(text, txtInd+1, pattern, patInd+1) || PatternMatch(text, txtInd, pattern, patInd+1) || PatternMatch(text, txtInd+1, pattern, patInd) ;
            else return false;
        }

- vj March 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>
#include<string.h>
int stringMatch(char * pattern , char * str ){
  int pointer=0;
  char c;
  int count;
  while ( pattern[0] != '\0' ){
    c=pattern[0];
    if ( pattern[1] == '*' ){
      count=-1;
      pattern+=2;
    } else {
      count=1;
      pattern+=1;
    }
    switch ( count ){
      case 1:
        if ( str[pointer] == c )
          pointer++;
        else
          return 0;
        break;
      case -1:
        while ( str[pointer] == c )
          pointer++;
    }
  }
  if ( pointer == strlen(str) )
    return 1;
  else
    return 0;
}

- gautam142857 April 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nope, won't work for a*a , aaa

- gautam142857 April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

is it not very similar to string compression ,, traverse the string... replace all similar symbols by symbol* .. do till end of string .. then compare with the given expression ... eg given string aaaaaaaabbbbbbbcccccc .. given expression a*b*c* .. traverse string till you reach b... replace all a's by a* same for b and then c.. compare with a*b*c* .. it matches .. hence true,,

- aryan shah April 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great Idea! Simple and elegant

- Deeps July 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@aryan this doesn't match string :"aaabba" reg:aa*bb*a

- kol July 11, 2012 | Flag


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