Google Interview Question 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.

- dumbhead on April 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sudhanshu on October 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good algo

- bp on September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 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 "";
}

- gimli on April 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- GKalchev on April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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?

- jpdasit17 on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Guest on September 02, 2012 | Flag
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.

- Mau on April 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Blahfoo on April 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i feel LRS should be "ababab" in this case

- bnm on April 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

some modification of KMP? rolling hash ?

- Anonymous on April 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

suffix tree

- Anonymous on April 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ran on April 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- alchu8 on May 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Second Attempt on September 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modification of KMP can do in O(n).

- Anonymous on September 27, 2012 | Flag
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)
					result.add(temp);
			}
			if(result.size() > 0)
				return result;
		}
		
		return result;
	}

- Suren on April 02, 2012 | Flag Reply
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)
					result.add(temp);
			}
			if(result.size() > 0)
				return result;
		}
		
		return result;
	}

- Suren on April 02, 2012 | Flag Reply
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?

- Anonymous on April 06, 2012 | Flag Reply
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.

- O(n) solution with suffix array on April 10, 2012 | Flag Reply
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;

}

- Anonymous on June 24, 2012 | Flag Reply
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;
    }

- Anonymous on August 15, 2012 | Flag Reply
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

- nybon on June 27, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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