Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 7 vote

Just do it recursively to check for all substrings.
boolean check(String s1, String s2){
if(s2.equals("*")) return true;
if(s1.equals(s2)) return true;
if(s2.charAt(0)=='?'){
return check(s1.substring(1),s2.substring(1))||check(s1,s2.substring(1));}
else if(s2.charAt(0)=='*'){
for(int i=0;i<=s1.length();i++){
if(check(s1.substring(i),s2.substring(1)) retun true;}
return false; }
else if(s1.charAt(0)!=s2.charAt(0)) return false;
return check(s1.substring(1),s2.substring(1));
}

- zyfo2 December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cool, one minor improvement would be just decreasing the number of recursive calls and getting rid of extra memory, here is my version(not working for a corner cases like "hello","*" but the idea seems to be right:

function match_internal(s1, s2, s1Index, s2Index){
  if(s1Index==s1.length && s2Index==s2.length)
    return true;
  while(s2[s2Index]!='*' && s2[s2Index]!='?' && s1Index < s1.length && s2Index < s2.length){
    if(s1[s1Index]!=s2[s2Index])
      return false;
    s1Index++;
    s2Index++;
  }
  if(s2[s2Index]=='?')
    return match_internal(s1, s2, s1Index, s2Index+1) || match_internal(s1,s2,s1Index+1, s2Index+1);
  if(s2[s2Index]=='*'){
    var zeroMatch = match_internal(s1, s2, s1Index, s2Index+1);
    if(zeroMatch)
      return true;
    var match = false;  
    for(var i=s1Index+1; i<s1.length;i++){
      match = match || match_internal(s1, s2, i, s2Index+1);
    }
    return match;
  }  
}

- S.Abakumoff December 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for your suggestions. Arrays are better in memory, but String also gets better equality comparison. I think your code already handles cases like "hello","*" if you just put the i<=s1.length. Besides you can also deal with it in the for loop of "*". I've modified my code to make it better.

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

@ zyfo2 I think there is a problem in your code. You have" s1.charAt(0)=='*' ", but the question means that s1 just contains from A to Z.

- amy January 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for your reminder. fixed it now.

- zyfo2 January 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It won't work if s1 contains duplicated chars.

- boba January 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tell me how does it work for "Abcde", "Acdef".

All the if conditions will fail, and the control will come to
return check(s1.substring(1),s2.substring(1));

Which will return true (check("A", "A")), which I think is wrong. Correct me if I am wrong.

Also, the * implementation is buggy

- Biru January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@S.Abakumoff As you mentioned we can store the already computed values in a hashtable and reduce number of recursive calls a lot. So the time complexity would be O(n*m) (n and m being the lengths of the two strings). (at the cost of O(n*m) space complexity.

- mjmirbagheri October 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

I am guessing its basically a question to implement regex matching algorithm.
For e.g if S1 = aabcccd & S2 = a*bc*d?e?. then its a match..

Assuming the S2 string is a proper regular expression then here's my algorithm

bool RegexMatch(char *S1, char* S2, int n1, int n2)
{
	int ptr1 = 0; int ptr2 = 0;

	while (ptr1 < n1 && ptr2 < n2)
	{
		if (S1[ptr1] == S2[ptr2]) 
		{
			ptr1++; ptr2++;
			if (S2[ptr2] == ?)
				ptr2++;
			if (ptr2 == *)
			{
				while(S1[ptr1-1] == S1[ptr1] && ptr1 < n1)
					ptr1++;
			}
		}
		else if (S2[ptr2+1] == *)
		{
			ptr2 = ptr2+2;			
		}
		else if (S2[ptr2+1] == ?)
		{
			ptr2 = ptr2+2;
		}
		else
		{
			return false;
		}
	}
	if (ptr1 < n1) return false;
	if (pt2 < n2) 
	{
		while(ptr2 < n2)
		{
			if (S2[ptr2] == * || S2[ptr2] == ?)
				ptr2++;
			else
			{
				if (S2[ptr2+1] == ? || S2[ptr2+1] == *)
					ptr2 = ptr2 + 2;
				else
					return false;
			}	
		}
	}
	return true;
}

- don December 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your Algorithm is absolutely correct.
The running code is:

#include<stdio.h>
#include<string.h>
int RegexMatch(char *S1, char* S2, int n1, int n2)
{
int ptr1 = 0; int ptr2 = 0;



while (ptr1 < n1 && ptr2 < n2)
{

if (S1[ptr1] == S2[ptr2])
{
ptr1++; ptr2++;
if (S2[ptr2] == '?')
ptr2++;
if (S2[ptr2] == '*')
{ ptr2++;
while(S1[ptr1-1] == S1[ptr1] && ptr1 < n1)
ptr1++;
}
}
else if (S2[ptr2+1] == '*')
{
ptr2 = ptr2+2;
}
else if (S2[ptr2+1] == '?')
{
ptr2 = ptr2+2;
}
else
{
return 0;
}
}
if (ptr1 < n1) return 0;
if (ptr2 < n2)
{
while(ptr2 < n2)
{
if (S2[ptr2] == '*' || S2[ptr2] == '?')
ptr2++;
else
{
if (S2[ptr2+1] == '?' || S2[ptr2+1] == '*')
ptr2 = ptr2 + 2;
else
return 0;
}
}
}
return 1;
}
int main()
{
char S1[]="aabcccd",S2[]="a*bc*d?e?";
int flag=RegexMatch(S1,S2,strlen(S1),strlen(S2));
if(!flag)
printf("Match Not Found\n");
else
printf("Match Found\n");
getch();
return 0;
}

Thanks Don!!! :)

- sonu December 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include "stdafx.h"
#include<stdio.h>
#include<string.h>

int RegexMatch(char *S1, char* S2, int n1, int n2)
{
int ptr1 = 0; int ptr2 = 0;

while (ptr1 < n1 && ptr2 < n2)
{

if (S1[ptr1] == S2[ptr2])
{
ptr1++; ptr2++;
}
else if (S2[ptr2] == '?')
{
if (S1[ptr1] != S1[ptr1 -1])
{
// skip * ?
while (ptr2 < n2 && (S2[ptr2] == '*' || S2[ptr2] == '?'))
{
++ptr2;
}
}
else
{
ptr1++; ptr2++;
}
}
else if (S2[ptr2] == '*')
{
if (S1[ptr1] != S1[ptr1 -1])
{
// skip * ?
while (ptr2 < n2 && (S2[ptr2] == '*' || S2[ptr2] == '?'))
{
++ptr2;
}
}
else
{
while(S1[ptr1] == S1[ptr1 - 1] && ptr1 < n1)
{
ptr1++;
}
++ptr2;
}
}
else
{
return 0;
}
}
if (ptr1 < n1) return 0;
return 1;
}

int main()
{
char S1[]="aaaabccd",S2[]="aa*bcc?d?e?"; // match
//char S1[]="aaaabcccd",S2[]="aa*bcc?*d?e?"; // match
//char S1[]="abccd",S2[]="aa*bcc?d?e?"; // not match
//char S1[]="aabccfd",S2[]="aa*bcc?d?e?"; // not match
int flag=RegexMatch(S1,S2,strlen(S1),strlen(S2));
if(!flag)
printf("Match Not Found\n");
else
printf("Match Found\n");
return 0;
}

- glk December 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please check if this code works for following example:
s1 = axyzbmnk
s2 =a*m?k
The output should be a match.

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

The question as phrased is not asking for regex match. If it were regex * would match the preceding character 0 or more times and ? would match the preceding character 0 or 1 times. The question says "any character" which means it is asking for a file name wildcard type of matching in which * fills in for any sequence of 0 or more characters and ? fills in for either no character or any one character. As in sr's comment, axyzbmnk and a*m?k should be a match.

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

BOOL matche(char *S1, char *S2){
    while(s2 && s1){
        if(*s2 == *s1){
	    return matche(++s1, ++s2);
	} else {
	    switch(*s2){
	        case '*':
                    while(*s2 == '*') s2++;
                    while(*s1) {if(match(++s1, s2) == TRUE) return TRUE;}
		    return FALSE;
		break;
		case '?':
		    ++s2;
                    if(match(s1, s2) == TRUE) return TRUE;
		    if(match(++s1, s2) == TRUE) return TRUE;
		break;
		default:
                     return FALSE;
		break;
	    }//switch
	}
    }//While
    if(*s2 == '*' || *s2 == '?') ++s2;
    if(*s1 == '\0')
        return TRUE;
    else return FALSE;
}

- SRB December 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

This problem can be efficiently solved using the modified dynamic algorithm for finding longest common sub-sequence.

The algorithm should be modified as follows:
Assume S1 is the the top row and S2 is the first column.
Then, the algorithm is allowed to move without penalty:
- diagonally if both are letters
- vertically (downwards) if '*' or '?'
- horizontally: only one step if '?' and many steps if '*'

For any other mismatch, penalize with infinity.

The strings match if there is a solution with cost less than infinity.

The cost of the algorithm is O(mn), m, n being the lenghts of S1 and S2.

The recursive algorithm mentioned here could have exponential time complexity.

- shantgk January 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What happens in the following case:

s1 = mmmmmm
s2 = m*m

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

adding another iterative solution to the pool

public static void main(String[] args) {
		System.out.println(matches("abcdefgh1", "a?d*"));
//		System.out.println(matches("axyzbmnk", "a*m?k"));
}

	public static boolean matches(String s1, String s2) {
		if (s1 == null || "".equals(s1))
			return false;
		if (s2 == null || "".equals(s2) || "*".equals(s2) || "?".equals(s2)) {
			return true;
		}
		String[] strArr2 = s2.split("\\*");
		List<List<String>> starList = new ArrayList<List<String>>();
		for (String str : strArr2) {
			List<String> qList = Arrays.asList(str.split("\\?"));
			starList.add(qList);
		}
		for (List<String> stars : starList) {
			for (int i=0;i<stars.size();i++) {
				String str = stars.get(i);
				int ind = s1.indexOf(str);
				if (ind < 0 || (i > 0 && ind > 1)) {
					return false;
				}
				s1 = s1.substring(ind + str.length());
			}
		}
		return true;
	}

- scr January 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool compS(char* s1,char* s2){
if(*s2=='\0'&&*s1=='\0')return true;
if(*s2=='?'){
return (compS(s1,s2+1)||compS(s1+1,s2+1));
}else if(*s2=='*'){
if(compS(s1,s2+1))return true;
char r=*s1;
if(r=='\0')return true;
while(*s1==r){
if(compS(s1+1,s2+1))return true;
++s1;
}
}else if(*s1==*s2)return compS(s1+1,s2+1);
return false;
}

- whenmary January 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean matches(char[] s, char[] p, int i, int j) {
		if (j < 0) {
			return i < 0;
		}
		if (i < -1)
			return false;
		if (i > -1 && s[i] == p[j]) {
			return matches(s, p, i - 1, j - 1);
		}
		if (p[j] == '?') {
			return matches(s, p, i, j - 1) || matches(s, p, i - 1, j - 1);
		}
		if (p[j] == '*') {
			return matches(s, p, i, j - 1) || matches(s, p, i - 1, j - 1)
					|| matches(s, p, i - 1, j);
		}
		return false;
	}

- A February 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean compareAnyStr(String s1, String s2) {
		return compareStr(s1.toUpperCase(), s2.toUpperCase());
	}
	public static boolean compareStr(String s1, String s2) {
		if(s1.length() == 0 || s2.length() == 0) {
			//if both are empty then return true
			if(s1.length() == 0 && s2.length() == 0) {
				return true;
			}
			
			//if s1 is empty and s2 is of length=1 and contains '*' then return true
			if(s1.length() == 0 && s2.length() == 1 && s2.charAt(0) == '*') {
				return true;
			}
			return false;
		}
		
		char ch2 = s2.charAt(0);
		if(ch2 >= 'A' && ch2 <= 'Z') {
			char ch1= s1.charAt(0);
			return (ch1 == ch2) && compareStr(s1.substring(1), s2.substring(1));
		} else {
			if(ch2 == '?') {
				//two cases: ? matches 0 character, ? matches 1 character of s1
				return compareStr(s1, s2.substring(1)) || 
						compareStr(s1.substring(1), s2.substring(1));
			} else {
				//two cases: * matches 0 character, * matches 1 character but we don't remove * from s2
				return compareStr(s1, s2.substring(1)) || 
						compareStr(s1.substring(1), s2);
			}
		}
	}
	
	public static void main(String[] args) throws CloneNotSupportedException {
		System.out.println(compareAnyStr("abc", "abc"));
		System.out.println(compareAnyStr("abc", "?bc"));
		System.out.println(compareAnyStr("abc", "*d"));
		System.out.println(compareAnyStr("abcde", "?bc*e"));
	}

- prashant2361 March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my solution in Java

public class Matches {


	// I named s2 as “regex”
	public static boolean matches(String s1, String regex) {

		// Pointers to the next character that should be examined
		int currentS1 = 0;
		int currentRegex = 0;

		while(currentS1 < s1.length() && currentRegex < regex.length()) {
			if(currentRegex + 1   <  regex.length() && regex.charAt(currentRegex + 1) == '?') {
				// means that regex.charAt(currentRegex)  should appear 1 or 0 times
				if(s1.charAt(currentS1) == regex.charAt(currentRegex)) {
					// advance s1’s pointer
					currentS1++;
				} 

				currentRegex +=2; // skip also the ‘?’


			}  else if(currentRegex + 1   <  regex.length() && regex.charAt(currentRegex + 1) == '*') {
				while(currentS1  < s1.length() &&  s1.charAt(currentS1) == regex.charAt(currentRegex)) {
					// advance s1’s pointer
					currentS1++;
				} 

				currentRegex +=2; // skip also the ‘*’


			} else {
				if(s1.charAt(currentS1) == regex.charAt(currentRegex)) {
					// advance s1’s pointer & regex’s pointer
					currentS1++;
					currentRegex++;
				} else {
					return false; // a mismatch was found
				}

			}

		} // while

		// reaching here means that at least one of the strings reached the end
		if(currentS1 >= s1.length() && currentRegex >= regex.length()) {
			return true; // both of the strings ended
		} else if(currentS1 >= s1.length() )  { // only the string has ended
			if(currentRegex == regex.length() -1)
				return false;
			
			currentRegex++;
			
			while(currentRegex < regex.length()) {
				if(regex.charAt(currentRegex) == '?' || regex.charAt(currentRegex) == '*'){
					// all of the expressions in the regex are either ? or *	
					//return true;
				} else {
					return false;
				}
				currentRegex += 2;
			}
			
			return true;
		} else {
			return false;
		}

	}
	
	public static void main(String[] args) {

		System.out.println("Should be true: "  + matches("aab","aab"));
		System.out.println("Should be true: "  + matches("aab","aab?"));
		System.out.println("Should be true: "  + matches("aa","aab?"));
		System.out.println("Should be true: "  + matches("aab","aab*"));
		System.out.println("Should be true: "  + matches("aa","aab*"));
		System.out.println("Should be true: "  + matches("aabbbbbbbbbb","aab*"));
		System.out.println("Should be true: "  + matches("aabbbbbbbbbbc","aab*c"));
		System.out.println("Should be true: "  + matches("aaaaaaaa","aa?a*"));
		System.out.println("Should be true: "  + matches("aaabbbbbcccccd","a*b*c*d*"));
		System.out.println("Should be true: "  + matches("aaabbbbbcccccd","a*b*c*d?"));
		System.out.println("Should be false: "  + matches("aaabbbbbcccccdd","a*b*c*d?"));
		System.out.println("Should be false: "  + matches("aaaaaaaa","b"));
		System.out.println("Should be false: "  + matches("aaaaaaaa","b?"));
		System.out.println("Should be false: "  + matches("aaaaaaaa","b*"));
		System.out.println("Should be false: "  + matches("ab","b*"));
		System.out.println("Should be false: "  + matches("abc","b*c"));


	}


}

- nonish May 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

And here is a simple dumb regex engine in python

def dumb_regex(str1, str2):
    #print str1, str2
    if str1 == str2:
        return True
    if str2 == '*':
        return True
    if len(str1) == 1 and str2 == '?':
        return True
    if str2[0] == '?':
        return dumb_regex(str1[1:], str2[1:]) or dumb_regex(str1, str2[1:])
    elif str2[0] == '*':
        for i in range(len(str1)):
            if dumb_regex(str1[i:], str2[1:]):
                return True
            else:
                return False
    elif str1[0] != str2[0]:
        return False
    return dumb_regex(str1[1:], str2[1:])
        

if __name__=="__main__":
    print dumb_regex('abcd', 'a*b*c?')
    print dumb_regex('abcd', 'a?b*c?')
    print dumb_regex('xyz', 'a?b*c?')
    print dumb_regex('xyzabcd', 'xy*')
    print dumb_regex('xyz', 'xy?')

- EK MACHCHAR May 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Output fo above run

True
True
False
True
True

- EK MACHCHAR May 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isMatch(const char *s, const char *p) {
  assert(s && p);
  if (*p == '\0') return *s == '\0';
 
  // next char is not '*': must match current character
  if (*(p+1) != '*') {
    assert(*p != '*');
    return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
  }
  // next char is '*'
  while ((*p == *s) || (*p == '.' && *s != '\0')) {
    if (isMatch(s, p+2)) return true;
    s++;
  }
  return isMatch(s, p+2);
}

- Z0nk3d August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isMatch(const char *s, const char *p) {
  assert(s && p);
  if (*p == '\0') return *s == '\0';
 
  // next char is not '*': must match current character
  if (*(p+1) != '*') {
    assert(*p != '*');
    return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
  }
  // next char is '*'
  while ((*p == *s) || (*p == '.' && *s != '\0')) {
    if (isMatch(s, p+2)) return true;
    s++;
  }
  return isMatch(s, p+2);
}

- Z0nk3d August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

return Pattern.matches(s1, s2);

- estif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Please give us some example for clarity and also tell us that in which case it will return true and in which case it will return false.

- sonu December 28, 2012 | 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