Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 6 vote

// The main function that checks if two given strings match. The first
// string may contain wildcard characters
bool match(char *first, char * second)
{
    // If we reach at the end of both strings, we are done
    if (*first == '\0' && *second == '\0')
        return true;
 
    // Make sure that the characters after '*' are present in second string.
    // This function assumes that the first string will not contain two
    // consecutive '*' 
    if (*first == '*' && *(first+1) != '\0' && *second == '\0')
        return false;
 
    // If the first string contains '?', or current characters of both 
    // strings match
    if (*first == '?' || *first == *second)
        return match(first+1, second+1);
 
    // If there is *, then there are two possibilities
    // a) We consider current character of second string
    // b) We ignore current character of second string.
    if (*first == '*')
        return match(first+1, second) || match(first, second+1);
    return false;
}

- Nit January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice... Very nice. I was asked the same question. Came up with DP solution but this is much simpler.

- DS January 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static bool Matches(string text, string pattern)
        {
            if (text == string.Empty && pattern == string.Empty)
                return true;
            
            int i = 0;
            for (; i < pattern.Length && i<text.Length; i++)
            {
                if (pattern[i] == '*')
                {
                    return Matches(text.Substring(i + 1), pattern.Substring(i)) || Matches(text.Substring(i + 1), pattern.Substring(i+1));
                }

                if(text[i] != pattern[i])
                    return false;
            }

            if (text.Length - 1 >= i || pattern.Length - 1 >= i)
                return false;

            return true;
        }

- BP January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

using recursion here is too expensive.

- chriscow January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static bool Match(string p, string s)
        {
            if (string.IsNullOrEmpty(p))
            {
                throw new ArgumentNullException("pattern cannot be null or empty");
            }

            int i = 0;
            while (p[i] != '*')
            {
                if (i >= s.Length || p[i] != s[i])
                {
                    return false;
                }

                i++;
                if (i == p.Length)
                {
                    throw new ArgumentException("Pattern doesn't have *");
                }
            }

            if (s.Length - i < p.Length - 1 - i)
            {
                return false; // s doesn't have enough leftover to compare
            }

            // Compare everything behind the *
            for (int j = 0; j < p.Length - 1 - i; j++)
            {
                if (p[p.Length - j - 1] == '*')
                {
                    throw new ArgumentException("multiple *s detected");
                }

                if (s[s.Length - j - 1] != p[p.Length - j - 1])
                {
                    return false;
                }
            }

            return true;
        }

- Anonymous January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean matches(String fileName, String singleStarPattern) throws FileNameFormatException, singleStarPatternFormatException {

        if(fileName.contains("*"))
            return false;

        if(singleStarPattern.indexOf("*") != singleStarPattern.lastIndexOf("*") || !singleStarPattern.contains("*"))
            return false;

        int startRun = 0;

        while (fileName.charAt(startRun) == singleStarPattern.charAt(startRun))
            startRun++;

        int endRun = singleStarPattern.length() - 1;

        int run = fileName.length() - 1;

        while (fileName.charAt(run) == singleStarPattern.charAt(endRun))
        {
            run --;
            endRun --;
        }

        return startRun == endRun;
    }

- Noori January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo: regex_matcher(s1, s2)
1. if s1 and s2 are empty return true
2. if *s1 and *s2 are same recurse for rest of the strings
3. if in wildcard string(s2) we find * we have option of skipping it and going ahead with next character or match one character in s1 and recurse
4. if none of the above matches return false

#include<iostream>

using namespace std;

bool regex_matcher(char *s1, char *s2)
{
    if(!*s1 && !*s2)
        return true;

    if(*s2 == '*' && *(s2+1) != '\0' && *s1 == '\0')
        return false;

    if(*s1 == *s2)
        return regex_matcher(s1+1, s2+1);

    if(*s2 == '*')
        return (regex_matcher(s1, s2+1) || regex_matcher(s1+1, s2));
    return false;
}

int main()
{
    bool matched = regex_matcher("index.html", "i*************x.htm*");
    if(matched)
        cout<<"matched"<<endl;
    else
        cout<<"not matched"<<endl;
    return 0;
}

- codeGeek January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean isMatch(String src, String pattern)
	{
		int src_index =0;
		int pattern_index = 0;
		while(src_index < src.length() && pattern_index < pattern.length())
		{
			if(pattern.charAt(pattern_index)=='*')
			{
				if(pattern_index+1 < pattern.length())
				{
					pattern_index++;
					while(src_index < src.length() && src.charAt(src_index)!=pattern.charAt(pattern_index))
					{
						src_index++;
					}
					if(src_index >= src.length())
						return false;
				}
				else
				{
					return true;
				}
			}
			else
			{
				pattern_index++;
				src_index++;
			}
		}
		if(pattern_index < pattern.length() || src_index < src.length())
			return false;
		else
			return true;
	}

- NachiketN.89 January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean isMatch(String src, String pattern)
	{
		int src_index =0;
		int pattern_index = 0;
		while(src_index < src.length() && pattern_index < pattern.length())
		{
			if(pattern.charAt(pattern_index)=='*')
			{
				if(pattern_index+1 < pattern.length())
				{
					pattern_index++;
					while(src_index < src.length() && src.charAt(src_index)!=pattern.charAt(pattern_index))
					{
						src_index++;
					}
					if(src_index >= src.length())
						return false;
				}
				else
				{
					return true;
				}
			}
			else
			{
				pattern_index++;
				src_index++;
			}
		}
		if(pattern_index < pattern.length() || src_index < src.length())
			return false;
		else
			return true;
	}

- NachiketN.89 January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't catch all the cases. The cases I found that it misses are:

<string> - <pattern>
"cat" - "cat**"
"cat" - "cat*"
"" - "*"
"cat" - "ca***t***"

- gus January 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean matches(String text , String pattern){
		int p_length = 0;
		for (int i = 0 ;i<pattern.length();++i){
			if (pattern.charAt(i)!='*'){
				p_length++;
			}
		}
		
		
		int i = 0 , j = 0;
		int txt_length = 0;
		boolean consecutive = false;
		while (i<text.length()&&j<pattern.length()){
			if (pattern.charAt(j)=='*'){				
				j++;
			}else{
				if (text.charAt(i)!=pattern.charAt(j)){
					 if (consecutive){
						 return false;
					 }
				}else{
					
					j++;
					txt_length++;
					consecutive = true;
				}		
			}					
		  i++;
		}
		
		return txt_length==p_length;

}

- Scott January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't catch all the cases. The cases I found that it misses are:

<string> - <pattern>
cat - *cat
cat - ca***t***

- gus January 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems to me this is mainly about catching all the "edge cases." I think I got them all but maybe not:

def match(str, pattern):
    if str != "" and pattern == "":
        return False

    if str == "" and pattern == "":
        return True

    if str == "" and pattern == "*":
        return True

    if pattern[0] == "*" and len(str) == 1 and len(pattern) > 1:
        return False

    if pattern[0] == str[0]:
        return match(str[1:], pattern[1:])

    if pattern[0] == "*":
        return match(str[1:], pattern) or match(str, pattern[1:])

    return False

- nilkn January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The recursive version that many have posted is elegant but not efficient since it performs backtracking. We can match any regex in a single scan, although it may be tricky. In my case, it was just a lot of tricky edge cases.

Here's my shot at it:

public static Boolean match(String string, String pattern) {
		int strIdx = 0;
		int patIdx = 0;
		int starIdx = -1;
		
		while(true) {
			if (strIdx == string.length()) {
				if (patIdx == pattern.length()) return true;
				else if (pattern.charAt(patIdx) == '*') {
					if (patIdx == pattern.length()-1) return true;
					else {
						patIdx++;
						continue;
					}
				}
				else return false;
			}
			else if (patIdx == pattern.length()) {
				return false;
			}
			else if (pattern.charAt(patIdx) == '*') {
				if (patIdx == pattern.length()-1) return true;
				starIdx = patIdx;
				patIdx++;
			}
			else if (string.charAt(strIdx) != pattern.charAt(patIdx)) {
				if (starIdx != -1) {
					patIdx = starIdx+1;
					strIdx++;
				}
				else return false;
			}
			else {
				strIdx++;
				patIdx++;
			}
		}
	}

- gus January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private boolean matches(String text, String pattern) {

if (text == null && pattern == null) return true;

if ((text != null && pattern == null) || (text==null && pattern!=null) ) return false;

for (int i=0;i<text.length()&&i<pattern.length();i++) {
if(pattern.charAt(i) == '*') {
return text.contains(pattern.substring(i+1));
} else (pattern.charAt(i) == text.charAt(i)) {
return matches(text.substring(i + 1), pattern.substring(i + 1));
}
}
return false;
}

- Anonymous January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static bool matches(string input, string pattern)
        {
            bool matches = true;

            if (pattern.Count(c => c == '*') != 1)
                return false;
            var parts = pattern.Split('*');
            if (parts.Length != 2)
                return false;
            bool isLeftSideNotEmpty = !String.IsNullOrEmpty(parts[0]);
            bool isRightSideNotEmpty = !String.IsNullOrEmpty(parts[1]);

            if (isLeftSideNotEmpty)
            {
                matches &= input.StartsWith(parts[0]);
            }

            if (isRightSideNotEmpty)
            {
                matches &= input.EndsWith(parts[1]);
            }

            Console.WriteLine(matches);
            return matches;
        }

- Paul Gedeon January 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we just have to find whether the left hand side string of * is a prefix and right hand size is a suffix. then we will need to find whether suffix.length + prefix.length < original_string.length or not. If * also allows blank characters we even will not need this check.

we have to assume that blank "" character is always a prefix and suffix.

- hirajhil January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Check if a given file name match a single-star pattern? (can't use regex I)
index.html matches *.html
foo.txt does not match *.html

matches("index.html", "*html") returns true
matches("foo.txt", "*html") returns false
matches("cat", "c*t") returns true
*/
public class Solution {

public static void main(String ... args) {
Solution sol = new Solution();
System.out.println(sol.isMatch("*", "hello.txt"));
System.out.println(sol.isMatch("he*", "hello.txt"));
System.out.println(sol.isMatch("*txt", "hello.txt"));
System.out.println(sol.isMatch("he*xt", "hello.txt"));
System.out.println(sol.isMatch("xx*", "hello.txt"));

}

private boolean isMatch(String singleStarPattern, String filename) {

int starIndex = singleStarPattern.indexOf("*");
if(starIndex == -1) { throw new IllegalArgumentException("Invalid pattern"); }
else if (singleStarPattern.length()==1) {return true;} // * matches everything
String prefix = singleStarPattern.substring(0, starIndex);
String suffix = singleStarPattern.substring(starIndex+1);

boolean prefixMatches=false, suffixMatches=false;
if(prefix.length()==0 || filename.startsWith(prefix)) { prefixMatches=true; }
if(suffix.length()==0 || filename.endsWith(suffix)) { suffixMatches=true; }

return prefixMatches && suffixMatches;
}

}

- amit.official January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
    Check if a given file name match a single-star pattern? (can't use regex I) 
    index.html matches *.html 
    foo.txt does not match *.html 
    
    matches("index.html", "*html") returns true 
    matches("foo.txt", "*html") returns false 
    matches("cat", "c*t") returns true
*/
public class Solution {
    
    public static void main(String ... args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("*", "hello.txt"));
        System.out.println(sol.isMatch("he*", "hello.txt"));
        System.out.println(sol.isMatch("*txt", "hello.txt"));
        System.out.println(sol.isMatch("he*xt", "hello.txt"));
        System.out.println(sol.isMatch("xx*", "hello.txt"));

    }

    private boolean isMatch(String singleStarPattern, String filename) {

        int starIndex = singleStarPattern.indexOf("*");
        if(starIndex == -1) { throw new IllegalArgumentException("Invalid pattern"); }
        else if (singleStarPattern.length()==1) {return true;} // * matches everything
        String prefix = singleStarPattern.substring(0, starIndex);
        String suffix = singleStarPattern.substring(starIndex+1);
        
        boolean prefixMatches=false, suffixMatches=false;
        if(prefix.length()==0 || filename.startsWith(prefix)) { prefixMatches=true; } 
        if(suffix.length()==0 || filename.endsWith(suffix)) { suffixMatches=true; } 
        
        return prefixMatches && suffixMatches;
    }

}

- amit.official January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If it is only one star, then only need to compare if the star & end equals the two parts in the pattern seperated by "*".
1. String[] strArr= pattern.split("\\*"); get two patterns for 'start with' and 'end with'.
2. just see if the string is start with strArr[0], and end with strArr[1].
3. some special cases, like empty...

- YL February 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In English (for the lazy), take the piece(s) of the query that are before, between, and after the wildcards, ie just the pieces that are not the wildcard, and strstr them in order against the body string. If / when you find a match for a piece, continue strstr'ing the next piece from the end of that match. This is O(N).

- JeffD February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

java code:

I assumed that if there is no star in the second String, false should be returned.

static boolean matches(String input, String star) {
	if (star.length()==0) return false;

	int p=0, q=0;
	while (p < input.length() && q < star.length() && star.charAt(q)!='*') { 
		//Move from begin to end until hit '*' 
		if (input.charAt(p++) != star.charAt(q++)) return false;
	}
	if (q==star.length()) //q==star.length() means no '*' in star
		return false; 

	int u=input.length()-1, v=star.length()-1;
	while (u >= 0 && v >= 0 && star.charAt(v) != '*') { 
		//Move from end to begin until hit '*'
		if (input.charAt(u--) != star.charAt(v--)) return false;
	}
	if (v < 0) //v<0 means no '*' in star
		return false; 

	//If there is a match with a single '*' in star
	//q and v should both end up at the position of '*'
	return q==v && star.charAt(q)=='*' && star.charAt(v)=='*'; 
}

Test cases:
"", "": false
"", "*": true
"abcde", "*": true
"abcde", "a*e": true
"abcde", "abc*de": true
"abcde", "*e": true
"abcde", "a*": true
"aaaaaaaaaa", "aa": false
"abababab", "ab": false
"abababab", "ab*b": true
"abababab", "ab***ab": false

- chriscow January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can't believe someone vote this fine code down!

- chriscow January 25, 2014 | 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