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

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.

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

Is this has to be case sensitive?

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)

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

Robin-Karp O(m+n)

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

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

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

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!

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?

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

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

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

}
}}

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

}
}

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.