Microsoft Interview Question


Country: India




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

This is O(n) solution

1. Read a pattern i.e substr within *. For example *abc*def*.doc* The first pattern is abc.
2. Use KMP algorithm to find if pattern exists in string and get starting and ending index of  where the pattern occurs in the main string.
3. Read the next pat, 
    Use  KMP again, 
     if it does not exist then no, 
      if it exists then check if starting index of this pattern is after the ending index of previous pattern. If so then continue with next pattern. Else no.

- artemis November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this will not work when we have multiple pattern substr in test string, for example :
test string is : "abcdeabchiabc"
pattern : *abc
Now according to your approach this will return no, but it should return true

- sonesh November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

and this is not a O(n) algo, it's complexity is O(n*strlen(max size sub-string in pattern)), which can be O(n*m) also in worst cases,

- sonesh November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sonesh To your 1st point..yes it will work..First the algo gets the pattern abc, then finds it right in the beginning of the main string.
To your 2nd point: what I mean was for each patter it is O(n)..of course it depends how many substrings need to be matched

- artemis November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we also need to see the order i.e first abc followed by def and then .doc
it should avoid the other string matchs

- jainrajrahul December 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

int isMatching(char *s,char *p)
{
	int si=0,pi=0,sl,pl;
	sl=strlen(s);
	pl=strlen(p);
	int star=-2;
	while(si<sl&&pi<pl)
	{
		if(p[pi]=='*')
			star=pi++;
		else if(p[pi]==s[si])
			pi++,si++;
		else
		{
			pi=star+1;
			if(p[pi]==s[si])       // if(p[pi]!=s[si])   this will also work, but will take an extra condition check when this 'if' is false
				pi++,si++;     //     si++;
			else
				si++;
		}
	}
	if(pi==pl)
		if(p[pi-1]=='*' || si==sl)
			return 1;
		else
			return 0;
	else
		if(p[pi]=='*' && pi+1==pl)
			return 1;
		else
			return 0;
}

- Parixit November 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can probably be optimized, here is my first attempt:

bool isMatching (const string &str, const string &pattern)
{
  vector <string> search;
  size_t cur_pos = 0;
  size_t prev_pos = -1;
  
  while ((cur_pos = pattern.find ("*", cur_pos)) != string::npos)
  {
    if (prev_pos != -1 && prev_pos != cur_pos)
    {
      search.push_back (pattern.substr (prev_pos, cur_pos - prev_pos));
    }
    prev_pos = ++cur_pos;
  }
  
  cur_pos = 0;
  for (const auto &x : search)
  {
    cur_pos = str.find (x, cur_pos);
    if (cur_pos == string::npos)
      return false;
    cur_pos++;
  }
  return true;
}

Note: Code written in C++11.

- Kyle November 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//	  codes-to-problem.blogspot.in/2012/11/write-function-to-check-given-string.html

public class isMatchingWithWildcard {
	public static void main(String [] args){
		String pattern = "*abc*def*.doc*";
		String str = "adsfabcxyzdefgh.do1docx";
		if(isMatching(str, pattern))
			System.out.print("Matching");
		else
			System.out.print("Not Matching");
	}
	
	public static Boolean isMatching(String str, String pattern){
		int l = pattern.length();
		if(pattern.lastIndexOf("*") == l-1)
			pattern= (String) pattern.subSequence(0, l-1);
		if(pattern.charAt(0) == '*')
			pattern= (String) pattern.subSequence(1, pattern.length());
		pattern = pattern.replace("*", "__");
		String [] patternArray = pattern.split("__");
		String sorttenString =str;
		for(String aPattern:patternArray){
			String [] temp = sorttenString.split(aPattern);
			if(temp.length==1 && (aPattern == patternArray[patternArray.length-1] 
					&& !sorttenString.toLowerCase().contains(aPattern.toLowerCase())))
				return false;
			str.substring(temp[0].length()+aPattern.length());
		}
		return true;
	}
}

- niraj.nijju November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Failing with this input:
"*abc*def*.doc*","adsfabcxyzdefgh.do.docxyz"

- Andi November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

giveing me wright result "matching"

- niraj.nijju November 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Here is my solution. It is recursive-based. I believe this approach is more easy to understand. (* this is written in c#)

public class WildcardMatcher
{
    public static bool isMatching(String str, String pattern)
    {
      if (0 == pattern.Length) {
        // basis case: when pattern is empty.
        // in this caes, only empty string is matched.
        
        return  0 == str.Length ? true : false;
      } else if (1 == pattern.Length) {
        // basis case: when pattern has only one character.
        // if it is '*', then all strings are matched.
        // if it is not '*', compare with str.
        
        if (pattern.Equals("*")) {
          return true;
        } else {
          return pattern.Equals(str);
        }
      } else {
        // recurssive case: pattern has more than 2 characters.
        
        char pattern_first_char = pattern[0];
        
        if ('*' == pattern_first_char) {
          // if the first character of pattern is '*'
          // find the first character in the pattern that is not '*'.
          // then, try matching with the substring of given string
          // that starts with the character.
          
          int i = 0;
          do {
            ++i;
          } while ('*' == pattern[i]);
          
          char pattern_next_char = pattern[i];
          String pattern_rest = pattern.Substring(i);
          
          for (int j = 0; j < str.Length; ++j) {
            if (pattern_next_char == str[j] && isMatching(str.Substring(j), pattern_rest)) {
              return true;
            }
          }
          
          return false;
        } else {
          // if the first character of pattern is not '*',
          // compare the first character of string & pattern.
          // if it matches, continue matching for rest part of string & pattern.
          
          char str_first_char = str[0];
          
          if (pattern_first_char == str_first_char) {
            String str_rest = str.Substring(1);
            String pattern_rest = pattern.Substring(1);
            
            return isMatching(str_rest, pattern_rest);
          } else {
            return false;
          }
        }
      }
    }
  }

- dongjin.lee.kr November 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if you are willing to use the API (methods) in the String class provided by C# then why not just use the Contains() method that support wild card search (which will make the solution even more ridiculous than yours) or why not split the pattern string with ' * ' character iterate througjh the splitted string array find the index of the current iterator value in the given string then search for the next iterator value in the substring from index of current iterator + iteratorValue.Length till the string end. This will as much ridiculous as your solution but much more neater code.

- The Artist November 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simplest way is to use split. Runtime: O(m+n)

public static boolean isMatch( String pattern, String str )
    {
        if( pattern == null || str == null )
            return false;
        
        String[] subpatterns = pattern.split("\\*");
        int pos = 0;
        
        for( int i = 0; i < subpatterns.length; i++ )
        {

        	if( pos >= str.length() )
        		return false;
        	
        	if( subpatterns[i].length() > 0 && pos < str.length() )
        	{
	        	int index = str.indexOf(subpatterns[i], pos );
	            if( index == -1 )
	            	return false;
	            else
	            	pos += subpatterns[i].length();
        	}
        }
        
        return true;
    }

- icoderttc December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StarPattern {

	public static boolean isMatch(String string, String pattern) {
		boolean isMatch = true;
		String[] patterns = pattern.split("\\*");
		int index = 0;
		int i;
		for (i = 0; i < patterns.length; i++) {
			if (string.substring(index).indexOf(patterns[i]) == -1) {
				isMatch = false;
				return isMatch;
			}
			index += string.substring(index).indexOf(patterns[i])
					+ patterns[i].length();
		}
		if (i != patterns.length) {
			isMatch = false;
		}
		// corner case detection
		if (pattern.charAt(0) != '*') {
			isMatch = string.startsWith(patterns[i-1]);
		}
		if (pattern.charAt(pattern.length() - 1) != '*') {
			isMatch = string.endsWith(patterns[i-1]);
		}
		return isMatch;
	}

	public static void main(String[] args) {
		String string = "adsfabcxyzdefgh.docx";
//		String string = "adsfabcxyzdefgh.do.docxyz";
		String pattern = "*abc*def*.doc*";
//		String string = "abcdeabchiabc";
//		String pattern = "*abc";
		System.out.println(isMatch(string, pattern));
	}

}

- Kevin March 02, 2013 | 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