## Google Interview Question for Software Engineer / Developers

Team: SRE
Country: India
Interview Type: Phone Interview

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

1. Build the suffix tree T.
2. Depth of a node v is measured by the number of characters from root to v. Calculate the depth of each node as : depth(v) = depth(v.parent) + length(v)
3.Now we need to look for the deepest branching node in the tree T.

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

building a suffix array would be more feasible and easier approach.
time complexity will be n*Log(n).

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

good algo

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

How does this solve for 'repeating' substring? Can anyone please explain. Thanks in advance.

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

How does this solve 'repeating' substring? Can anyone please explain. Thanks in advance.

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

I implemented it using KMP longest prefix finding approach.

Basically, I am finding the longest prefix of all substrings of the given string, which is proper suffix of the substring.

More clearly, for any substring s[i] ... s[j], I find the longest prefix s[i] ... s[k] which is proper suffix of s[i] ... s[j].

When, I have computed all such values, I go over them and check if the prefix found is a repeating string (it is, if the length of prefix is atleast half the length of the substring considered), and return the longest one.

Since I have to find for all strings, the running time is O(n^2). Is there any better time complexity? I am think maybe I can use the result of pi[0][x] ... pi[i-1][x] while computing pi[i][x], but having thought through it.

``````static string FindLongestRepeationgSubstring(string s)
{
int n = s.length();
int pi[n][n];
for (int i = 0; i < n; ++i)
pi[i][i] = i - 1;

for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
int k = pi[i][j-1];
while (k >= i && s[j] != s[k+1]) k = pi[i][k];

if (s[j] == s[k+1]) k++;

pi[i][j] = k;
}
}

for (size_t i = 0; i < n; ++i)
{
for (size_t j = i; j < n; ++j)
{
cout << pi[i][j] << " ";
}
cout << endl;
}

int ls = -1;
int le = -1;
int l = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
int tempL = pi[i][j] - i + 1;
if ((pi[i][j] >= j - tempL) && tempL > l)
{
l = tempL;
ls = i;
le = pi[i][j];
}
}
}

if (l > 0)
return s.substr(ls, l);
else
return "";
}``````

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

this is a good idea and can be easily coded during the interview.

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

@gimli: i didn't understand the following:
"it is, if the length of prefix is atleast half the length of the substring considered".
We are looking for a repeated string .Why half length?

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

The Failure function in KMP, gives the longest suffix which is also a prefix, i think that would be sufficient to find the longest common substring in given string in O(n)

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

I don't understand why "aba" and "bab" are the longest repeating strings; I would think of "abab" as the longest one.

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

I am sorry. I must be in a brain freeze today, it is indeed 'abab'.

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

i feel LRS should be "ababab" in this case

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

some modification of KMP? rolling hash ?

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

suffix tree

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

@bnm - The question reads repeating substring,So it would be abab and not ababab.

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

What's repeated here is the substring "ab". "abab" is a repetition of "ab". The meaning of "longest" repeating substring means the longest substring consisted of a unique pattern that is repeated later on. "ab" is the longest of a unique pattern that is repeated.

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

@alchu8 u're right..Longest repeated substring should be "ab". If we create suffix tree of "ababab" then there is only 1 branching of length 2.

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

Modification of KMP can do in O(n).

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

``````public static void main(String[] args) {
String input = "ababab";
List<String> result = getLongestString(input);
for(String str : result)
System.out.println(str);
}

private static List<String> getLongestString(String input) {
ArrayList<String> result = new ArrayList<String>();

for(int i=input.length()-1; i>0; i--) {
String tempStr = null;
for(int j=0; j<=input.length()-i; j++) {
String temp = input.substring(j, i+j);

tempStr = input.substring(0, i+j-1);
if(tempStr.indexOf(temp) > -1)
}
if(result.size() > 0)
return result;
}

return result;
}``````

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

``````public static void main(String[] args) {
String input = "ababab";
List<String> result = getLongestString(input);
for(String str : result)
System.out.println(str);
}

private static List<String> getLongestString(String input) {
ArrayList<String> result = new ArrayList<String>();

for(int i=input.length()-1; i>0; i--) {
String tempStr = null;
for(int j=0; j<=input.length()-i; j++) {
String temp = input.substring(j, i+j);

tempStr = input.substring(0, i+j-1);
if(tempStr.indexOf(temp) > -1)
}
if(result.size() > 0)
return result;
}

return result;
}``````

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

I can think of an O(N^2) algorithm. any better sol?

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

see Suffix_array in wikipedia

Construct a sorted suffix array with lcp in O(n) time. (It seems impossible to code this during interview).

Then for each suffix i, the maximum repeated substring is the lcp with i-1 or i+1. Since lcp is already computed, so for each suffix i, we can compute the repeated substring in O(1) time. Thus totally O(n) time.

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

``````char * longest_substring(char * string, int length)
{
if(string == NULL)
{
return NULL;
}
char * result = NULL;
int begin_str, end_str, count, max_begin, max_end, max_count=0;
int max_length = 0;
int end =0;
for(begin_str = 0; begin_str < length-1; begin_str ++)
{
for(end_str = begin_str; end_str < length-1; end_str++)
{
count = 0;
int i,k;

k=end_str +1;
end = 0;
do{

for(i = begin_str; i <=end_str && k < length && string[k] == string[i]; i ++, k++);
if(i > end_str)
{
count ++;
end = k-1;
}
}while(i > end_str);

if(end-begin_str > max_count)
{
max_length = (end_str - begin_str);
max_count = k-begin_str;
max_begin=begin_str;
max_end = end;
}
}
}
result = new char[max_end-max_begin+1];
int k =0;
for(int i = max_begin; i <=max_end; i ++,k++)
{
result[k] = string[i];
}
result[k] = '\0';
return result;

}``````

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

This use brutal force method, which go for all combinations. the running time would be O(n^3)

``````public String findRepeat(String input){
if(input == null || input.length() < 2){
System.out.println("String is null or string length is less then 2");
return null;
}

int longestStart = 0;
int longestEnd = 0;
for(int repeatLen = input.length()/2; repeatLen > 0; repeatLen--){
for(int i=0; i + repeatLen*2 <= input.length(); i++){
int start = i;
int end = i;
for(int curr = i; curr + repeatLen*2 <= input.length(); curr+=repeatLen){
if(compareStr(input.substring(curr, curr+repeatLen), input.substring(curr+repeatLen, curr+repeatLen*2))){
if(start == end){
start = curr;
end = curr+repeatLen*2;
if(end - start > longestEnd - longestStart){
longestStart = start;
longestEnd = end;
}
}else if(end >= curr){
end = curr+repeatLen*2;
if(end - start > longestEnd - longestStart){
longestStart = start;
longestEnd = end;
}
}else{
start = curr;
end = curr+repeatLen*2;
}
}
}

}
}
if(longestStart < longestEnd){
return input.substring(longestStart,longestEnd);
}
return null;

}
public boolean compareStr(String a, String b){
if( a == null || b == null){
System.out.println("One of string is null!");
return false;
}
if(a.length() != b.length()){
return false;
}
for(int i=0; i<a.length(); i++){
if(a.charAt(i) != b.charAt(i)){
return false;
}
}
return true;
}``````

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

* Longest repeated substring
** en.wikipedia.org/wiki/Longest_repeated_substring_problem, linear time solution using suffix tree
** KMP partial match function solution seems to give an O(n^2) solution only
** Suffix array can solve this problem in O(nlgn)
*** algs4.cs.princeton.edu/63suffix/
*** algs4.cs.princeton.edu/63suffix/LRS.java.html

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.