Google Interview Question
Software EngineersTeam: Search
Country: United States
Interview Type: In-Person
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;
}
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!
#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);
}
#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);
}
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