Google Interview Question for Software Engineers


Team: Search
Country: United States
Interview Type: In-Person




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

They wanted Naive/KMP solution or SuffixArray/SuffixTree. You could just code any substring and then talk about scalability and very big strings. But your is N*N. Nice hack about tracker. But it N*N.

- coder February 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Look up the Rabin-Karp Algorithm and Knuth-Morris-Pratt Algorithm for ways to optimize this.

- randythai1996 February 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this has to be case sensitive?

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

You can using sliding window concept for this problem. It would be O(n)

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

Robin-Karp O(m+n)
Credit to Tushar Roy, can't add the link

private int prime = 101;
    
    public int patternSearch(char[] text, char[] pattern){
        int m = pattern.length;
        int n = text.length;
        long patternHash = createHash(pattern, m - 1);
        long textHash = createHash(text, m - 1);
        for (int i = 1; i <= n - m + 1; i++) {
            if(patternHash == textHash && checkEqual(text, i - 1, i + m - 2, pattern, 0, m - 1)) {
                return i - 1;
            }
            if(i < n - m + 1) {
                textHash = recalculateHash(text, i - 1, i + m - 1, textHash, m);
            }
        }
        return -1;
    }
    
    private long recalculateHash(char[] str,int oldIndex, int newIndex,long oldHash, int patternLen) {
        long newHash = oldHash - str[oldIndex];
        newHash = newHash/prime;
        newHash += str[newIndex]*Math.pow(prime, patternLen - 1);
        return newHash;
    }
    
    private long createHash(char[] str, int end){
        long hash = 0;
        for (int i = 0 ; i <= end; i++) {
            hash += str[i]*Math.pow(prime,i);
        }
        return hash;
    }
    
    private boolean checkEqual(char str1[],int start1,int end1, char str2[],int start2,int end2){
        if(end1 - start1 != end2 - start2) {
            return false;
        }
        while(start1 <= end1 && start2 <= end2){
            if(str1[start1] != str2[start2]){
                return false;
            }
            start1++;
            start2++;
        }
        return true;
    }

- Ahmed Abouhegaza February 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_substring_index(str1, str2, index=0):

    if len(str1) < len(str2):
        return -1
    elif str1[:len(str2)] == str2:
        return index
    else:
        return find_substring_index(str1[1:], str2, index + 1)

- TJ March 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_substring_index(str1, str2, index=0):

    if len(str1) < len(str2):
        return -1
    elif str1[:len(str2)] == str2:
        return index
    else:
        return find_substring_index(str1[1:], str2, index + 1)

- TJ March 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I came up with this solution, which is similar to OP but is a bit more optimized, would this be wrong?

public int isSubstring(String s, String x){
	int size = x.length();
	for(int i = 0; i < s.length() - size+1; i++){
		if(s.charAt(i) == x.charAt(0)){
			String check = s.substring(i , i+size);
			if(check.equals(x)){
				return i;
			}
		}
	}
	return -1;
}

I'm sure it is just O(n) at worst well kinda more like O(n-x) if you account for the size of the string being searched for

Let me know what you guys think!

- AwesomeCoder411 April 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

so basically this comes down to weather you knew KMP algorithm from before... or does Google expect candidates to invent KMP from scratch in real time?

- rick April 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
using namespace std;
int* GetLps(string pattern)
{
int size = pattern.length();
int* lps = new int[size];
lps[0] = 0;
for(int i=1; i<size; i++)
{
int length = lps[i-1];
while(length > 0)
{
if(pattern[i] == pattern[length])
{
lps[i] = length + 1;
break;
}
else
{
length = lps[length-1];
}
}
if(length == 0)
{
if(pattern[0] == pattern[i])
{
lps[i] = 1;
}
else
{
lps[i] = 0;
}
}
}
return lps;
}

int SearchIndex(string s, string x)
{
int* lps = GetLps(x);
int i=0;
int j=0;
int length1 = s.length();
int length2 = x.length();
while(i < length1)
{
if(s[i] == x[j] && j == length2-1)
{
return i-length2+1;
}
else if(s[i] == x[j])
{
i++;
j++;
}
else
{
j = lps[j];
i++;
}
}
return -1;
}

int main() {
string s;
cin>>s;
string x;
cin>>x;
cout<<SearchIndex(s, x);
}

- Anonymous February 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
using namespace std;
int* GetLps(string pattern)
{
	int size = pattern.length();
	int* lps = new int[size];
	lps[0] = 0;
	for(int i=1; i<size; i++)
	{
		int length = lps[i-1];
		while(length > 0)
		{
			if(pattern[i] == pattern[length])
			{
				lps[i] = length + 1;
				break;
			}
			else
			{
				length = lps[length-1];
			}
		}
		if(length == 0)
		{
			if(pattern[0] == pattern[i])
			{
				lps[i] = 1;
			}
			else
			{
				lps[i] = 0;
			}
		}
	}
	return lps;
}

int SearchIndex(string s, string x)
{
	int* lps = GetLps(x);
	int i=0;
	int j=0;
	int length1 = s.length();
	int length2 = x.length();
	while(i < length1)
	{
		if(s[i] == x[j] && j == length2-1)
		{
			return i-length2+1;
		}
		else if(s[i] == x[j])
		{
			i++;
			j++;
		}
		else
		{
			j = lps[j];
			i++;
		}
	}
	return -1;
}

int main() {
	string s;
	cin>>s;
	string x;
	cin>>x;
	//int* lps = GetLps(s);
	cout<<SearchIndex(s, x);
}

- Anonymous February 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

String s = "AGoddddsAw";
String x ="sAw";
char[] value = s.toCharArray();
if(s.length()==x.length()) {
//return with expected value
}
for(int i=0;i<=value.length-x.length();i++) {
if(new String(value, i,x.length()).equals(x)) {
System.out.println(true);break;
};

}
}}

- Satish February 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{

String s = "AGoddddsAw";
String x ="sAw";
char[] value = s.toCharArray();
if(s.length()==x.length()) {
//return with expected value
}
for(int i=0;i<=value.length-x.length();i++) {
if(new String(value, i,x.length()).equals(x)) {
System.out.println(true);break;
};

}
}

- Satish February 28, 2019 | 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