## Microsoft Interview Question

• 0

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.
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.``````

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

Comment hidden because of low score. Click to expand.
0

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,

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

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.

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*";
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;
}
}``````

Comment hidden because of low score. Click to expand.
0

Failing with this input:

Comment hidden because of low score. Click to expand.
0

giveing me wright result "matching"

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;
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

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;
}``````

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 pattern = "*abc*def*.doc*";
//		String string = "abcdeabchiabc";
//		String pattern = "*abc";
System.out.println(isMatch(string, pattern));
}

}``````

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.