## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

``````public static boolean isMatch(String str, String pattern)	{
int n = str.length();
int m = pattern.length();

if (m == 0 && n == 0) return true;

boolean[][] t = new boolean[n + 1][m + 1];

for(int i = 0; i < n + 1; i++)
Arrays.fill(t[i], false);

t[0][0] = true;

for (int j = 1; j <= m; j++) {
if (pattern.charAt(j - 1) == '*' || (pattern.charAt(j - 1) == '+')) {
t[0][j] = t[0][j - 1];
}
}

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (pattern.charAt(j - 1) == '*') {
t[i][j] = t[i][j - 1] || t[i - 1][j];
}
else if (pattern.charAt(j - 1) == '+') {
t[i][j] = t[i][j - 1] || t[i - 1][j - 1];
}
else if (str.charAt(i - 1) == pattern.charAt(j - 1)) {
t[i][j] = t[i - 1][j - 1];
}
else {
t[i][j] = false;
}
}
}

return t[n][m];
}``````

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

``````#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <deque>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

typedef string::iterator iter;

bool reg(iter is, iter ie, iter rs, iter re){

if(is == ie && rs == re)
return true;

if(is == ie && rs != re){
if(*rs == '+') return reg(is,ie,++rs,re);
if(*rs == '*') return reg(is,ie,++rs,re);
return false;
}

if(is != ie && rs == re)
return false;

if(*rs == '+')
return reg(++is,ie,++rs,re);

if(*rs == '*'){
bool r;
rs++;
while(is != ie){
r |= reg(++is,ie,rs,re);
}
return r;
}

if(*is == *rs)
return reg(++is,ie,++rs,re);

if(*is != *rs)
return false;

}
//just a wrapper
bool isMatch(string s, string regx){
cout << "Checking " << s << " against " << regx << " ... ";

if(reg(s.begin(), s.end(), regx.begin(), regx.end())){
cout << "MATCH !" << endl;
return true;
}else{
cout << "no match found." <<endl;
return false;
}
}

int main(){
string text = "baaabab";

isMatch(text, "ba*a++");
isMatch(text, "ba*a+");
isMatch(text, "a*ab");
isMatch("","+");

}``````

Output:

Checking baaabab against ba*a++ ... MATCH !
Checking baaabab against ba*a+ ... MATCH !
Checking baaabab against a*ab ... no match found.
Checking against + ... MATCH !

...Program finished with exit code 0
Press ENTER to exit console.

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

What is your "bool r" initialized to?" I think there is a need to initialize that and initial value may decide true/false.

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

``````#include <iostream>
#include <string>

using namespace std;

typedef string::iterator iter;

bool reg(iter is, iter ie, iter rs, iter re){

//cout << *is << " " << *rs << endl;

if(is == ie && rs == re)
return true;

if(is == ie && rs != re){
if(*rs == '+') return reg(is,ie,++rs,re);
if(*rs == '*') return reg(is,ie,++rs,re);
return false;
}

if(is != ie && rs == re)
return false;

if(*rs == '+')
return reg(++is,ie,++rs,re);

if(*rs == '*'){
bool r;
rs++;
while(is != ie){
r |= reg(++is,ie,rs,re);
}
return r;
}

if(*is == *rs)
return reg(++is,ie,++rs,re);

if(*is != *rs)
return false;

}
//wrapper
bool isMatch(string s, string regx){
cout << "Checking " << s << " against " << regx << " ... ";

if(reg(s.begin(), s.end(), regx.begin(), regx.end())){
cout << "MATCH !" << endl;
return true;
}else{
cout << "no match found." <<endl;
return false;
}
}

int main(){
string text = "baaabab";

isMatch(text, "ba*a++");
isMatch(text, "ba*a+");
isMatch(text, "a*ab");
isMatch("","+");

}``````

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

``````#include <iostream>
#include <string>

using namespace std;

typedef string::iterator iter;

bool reg(iter is, iter ie, iter rs, iter re){

//cout << *is << " " << *rs << endl;

if(is == ie && rs == re)
return true;

if(is == ie && rs != re){
if(*rs == '+') return reg(is,ie,++rs,re);
if(*rs == '*') return reg(is,ie,++rs,re);
return false;
}

if(is != ie && rs == re)
return false;

if(*rs == '+')
return reg(++is,ie,++rs,re);

if(*rs == '*'){
bool r;
rs++;
while(is != ie){
r |= reg(++is,ie,rs,re);
}
return r;
}

if(*is == *rs)
return reg(++is,ie,++rs,re);

if(*is != *rs)
return false;

}
//wrapper
bool isMatch(string s, string regx){
cout << "Checking " << s << " against " << regx << " ... ";

if(reg(s.begin(), s.end(), regx.begin(), regx.end())){
cout << "MATCH !" << endl;
return true;
}else{
cout << "no match found." <<endl;
return false;
}
}

int main(){
string text = "baaabab";

isMatch(text, "ba*a++");
isMatch(text, "ba*a+");
isMatch(text, "a*ab");
isMatch("","+");

}``````

Output:

Checking baaabab against ba*a++ ... MATCH !
Checking baaabab against ba*a+ ... MATCH !
Checking baaabab against a*ab ... no match found.
Checking against + ... MATCH !

...Program finished with exit code 0
Press ENTER to exit console.

P.S. Sorry for the spam above, couldn't tell if the post worked or not...dang it.

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

``````//C#

public static class Regex
{
public static bool IsMatch(string text, string regex)
{
if (regex.Length == 0)
return text.Length == 0;

if (regex[0] == '+')
return (IsMatch(text, regex.Substring(1)) || text.Length > 0 && IsMatch(text.Substring(1), regex.Substring(1)));

if (regex[0] == '*')
if (text.Length > 0)
for (int i = text.Length - 1; i > -1; i--)
{
if (IsMatch(text.Substring(i), regex.Substring(1)))
return true;
}
else return true;

if (text.Length > 0 && text[0] == regex[0])
return IsMatch(text.Substring(1), regex.Substring(1));

return false;
}
}``````

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

for String = "aaa" and regex="a*" your code ans is false :/

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

In addition we need to get true for IsMatch("aabc","a+++bc") need to get true
and for IsMatch(" ","+++")

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

If you start thinking recursive it's easy:
- for the +: must advance the pattern, but two options with the string, advance or not
- if not + and not *: if they match advance pattern and string
- termination: if pattern reached the end but string didn't (no match), if both reached the end (match)
do not forget all the border cases, so there is no buffer overrun

``````#include <iostream>
#include <string>

using namespace std;
using iter = string::iterator;

bool reg(iter is, iter ie, iter rs, iter re)
{
if (is == ie && rs == re) return true;
if (rs == re) return false;

if (*rs == '+') {
if (reg(is, ie, rs + 1, re)) return true; // advance pattern but not input (empty character)
return (is != ie) && reg(is + 1, ie, rs + 1, re); // advance input and pattern, if input not at the end
}
if (*rs == '*') {
if (reg(is, ie, rs + 1, re)) return true; // advance pattern but not input (empty sequence)
return (is != ie) && (reg(is + 1, ie, rs, re) || reg(is + 1, ie, rs + 1, re)); // advance input but not patter OR advance input and pattern
}
return (is != ie) && (*is == *rs) && reg(is + 1, ie, rs + 1, re); // if they match recurse
}

void test(string s, string regx, bool match) {
cout << "TEST CASE input: '" << s << "' expression '" << regx << "'"
<< (reg(s.begin(), s.end(), regx.begin(), regx.end()) == match ? " PASSED" : " FAILED")
<< endl;
}

int main() {
test("baaabab", "ba*a++", true);
test("baaabab", "ba*a+", true);
test("baaabab", "a*ab", false);
test("", "", true);
test("1", "", false);
test("", "+", true);
test(" ", "+", true);
test(" ", "+*", true);
test(" ", "+++", true);
test(" ", "+**", true);
test("", "+**", true);
test("", "+**+", true);
test("a", "+**+", true);
test("zzaazzuu", "+**+", true);
test("zzaazzuup", "+*p*+", true);
test("zzaazzuup", "+a**+", false);
test("aaaaaa", "+**", true);
test("aaaabbba", "+**", false);
test("aabc", "a+++bc", true);

return 0;
}``````

so what's space and runtime complexity (n is length string, m is length pattern)
space is the stack, and the stack depth will never exceed O(m + n) (actually O(max(n,m)) because it will always follow a branch to the end where it fails latest or succeeds.

worst case time is trickier:
- theoretically it branches of at the * case three times O(3 ^ (n + m))
- practically string: zzzq, pattern: ***z

how to improve is an interesting discussion here:
- preprocessing the pattern to only test the suffix if prefixes are common: this is not trivial with the * and +
- creating an automaton, in it's core the same as above
- no of them is trivial, there is a simpler dp way hidden in the recursion so one can prune some branches for example, if the pattern position and string position has already been senn, one can store the result already obtained. That way it should come down to O(m*n) when adding memoization.

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

``````private bool IsMatch(string str, string regex, int strIndex, int regexIndex)
{
if (strIndex == str.Length && regexIndex == regex.Length) //we reached the end of the string and the regex
return true;
var i = strIndex;
var j = regexIndex;

// Advance while the two characters are identical
while (i < str.Length && j < regex.Length && str[i] == regex[j])
{
i++;
j++;
}

if (i == str.Length && j == regex.Length) return true; // we reached the end of the string and regex

if (i == str.Length) //we are at the end of the string, if the regex are all */+ then we are good
{
for (; j < regex.Length; j++)
if (regex[j] != '+' && regex[j] != '*') return false;

return true; // the remaining of the regex is all * and/or +
}

// Case 1: we recahed the end of the regex but not of the string
// Case 2: this means both are not empty and the first non-matching is neither * nor +
if (j == regex.Length || regex[j] != '+' && regex[j] != '*') return false;

if (regex[j] == '+')
return IsMatch(str, regex, i + 1, j + 1) || IsMatch(str, regex, i, j + 1);

// it has to be '*'
return IsMatch(str, regex, i, j + 1) || IsMatch(str, regex, i + 1, j) || IsMatch(str, regex, i + 1, j + 1);
}``````

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

``````def match(s, p):
n = len(s)
m = len(p)
ms = [[False] * (m + 1) for _ in xrange(n + 1)]
ms[0][0] = True
for j in xrange(1, m+1):
ms[0][j] = ms[0][j-1] and p[j-1] in ['*', '+']
for i in xrange(1, n+1):
for j in xrange(1, m+1):
if p[j-1] == '*':
ms[i][j] = ms[i][j-1] or ms[i-1][j]
elif p[j-1] == '+':
ms[i][j] = ms[i][j-1] or ms[i-1][j-1]
else:
ms[i][j] = p[j-1] == s[i-1] and ms[i-1][j-1]
return ms[n][m]``````

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

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}

public class Pattern {

private string text;
private int posText;
private string patt;
private int posPatt;

public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}

public bool getResult() {

while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}

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

``````//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}

public class Pattern {

private string text;
private int posText;
private string patt;
private int posPatt;

public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}

public bool getResult() {

while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}``````

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

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}

public class Pattern {

private string text;
private int posText;
private string patt;
private int posPatt;

public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}

public bool getResult() {

while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}

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

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}

public class Pattern {

private string text;
private int posText;
private string patt;
private int posPatt;

public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}

public bool getResult() {

while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}

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

``````//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
Console.WriteLine("Hello, world!");
Pattern pattern = new Pattern("baaababc", 0, "ba*a+c", 0);
bool result = pattern.getResult();
Console.WriteLine(result.ToString());
}
}

public class Pattern {

private string text;
private int posText;
private string patt;
private int posPatt;

public Pattern(string text, int posText, string patt, int posPatt) {
this.text = text;
this.posText = posText;
this.patt = patt;
this.posPatt = posPatt;
}

public bool getResult() {

while(posPatt != patt.Length) {
if (posText >= text.Length) return false;
if (patt[posPatt] == text[posText]) {
posPatt++;
posText++;
continue;
}
if (patt[posPatt] == '*') {
posPatt++;
for (int i = posText+1; i < text.Length; i++) {
Pattern pattern = new Pattern(text, i, patt, posPatt);
if (pattern.getResult()) return true;
}
continue;
}
if (patt[posPatt] == '+') {
posPatt++;
Pattern pattern = new Pattern(text, posText+1, patt, posPatt);
if (pattern.getResult()) return true;
continue;
}
return false;
}
if (posText == text.Length) return true;
return false;
}
}
}``````

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

O(nm) time and space.

``````#include <string>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

bool Match(const string& s, const string& p, unordered_map<uint64_t, bool>& memo, int idx_s = 0, int idx_p = 0)
{
if (idx_s < 0 ||
idx_s > s.size() ||
idx_p < 0 ||
idx_p > p.size())
{
return false;
}
if (idx_s == s.size() &&
idx_p == p.size())
{
return true;
}
if (idx_s == s.size())
{
if (p[idx_p] == '*' ||
p[idx_p] == '+')
{
return Match(s, p, memo, idx_s, idx_p + 1);
}
else
{
return false;
}
}
if (idx_p == p.size())
{
return !p.empty() && p.back() == '*';
}

uint64_t memo_key = (static_cast<uint64_t>(idx_s) << 32) | idx_p;
auto it = memo.find(memo_key);
if (it != memo.end())
{
return it->second;
}

bool res = false;
if (p[idx_p] == '*')
{
for (int i = idx_s + 1; i <= s.size() && !res; ++i)
{
res |= Match(s, p, memo, i, idx_p);
}
if(!res)
{
res = Match(s, p, memo, idx_s, idx_p + 1);
}
}
else if (p[idx_p] == '+')
{
res = Match(s, p, memo, idx_s + 1, idx_p + 1) |
Match(s, p, memo, idx_s, idx_p + 1);
}
else
{
res = s[idx_s] == p[idx_p]
? Match(s, p, memo, idx_s + 1, idx_p + 1)
: false;
}
memo[memo_key] = res;
return res;
}

int main()
{
vector<pair<string, string>> test_cases =
{
{"baaabab", "ba*a++"},
{"baaabab", "ba*a+"},
{"baaabab", "a*ab"},
{"", "+"},
{"baaabab", "ba+"},
{"baaabab", "ba*"},
{"ba", "*+**++a+*+**++"}
};
unordered_map<uint64_t, bool> memo;
for (auto t : test_cases)
{
memo.clear();
cout << Match(t.first, t.second, memo) << "\n";
}
return 0;
}``````

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.