Google Interview Question for SDE1s


Country: United States
Interview Type: In-Person




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

Something like this should be ok..
The program should be pretty much self explanatory
Hope this helps

static String string;

public static void main(String[] args) {
    System.out.print("Enter the string : ");
    string = (new Scanner(System.in)).nextLine();
    for (int i = 0; i < string.length(); i++)
        System.out.println("S(" + (i + 1) + "," +
                string.length() + ") = " + S(i, string.length()));
    for (int i = 0; i < string.length(); i++)
        System.out.println("len(LCP(s(" + (i + 1) + "," +
                string.length() + "),s)) = " +
                LCP(S(i, string.length()), string).length());
}

static String S(int start, int end) {
    return string.substring(start, end);
}

static String LCP(String a, String b) {
    for (int i = a.length(); i > 0; i--) {
        String tmp = a.substring(0, i);
        if (b.startsWith(tmp)) return tmp;
    }
    return "";
}

- PeyarTheriyaa December 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is not valid because it does not take linear time. The question specifically specified "Find the LCP lengths of *all substrings* in O(n)".

This one clearly is at least O(n^2) time. There's a loop calling LCP n times, and LCP itself both has a loop and a call to startsWith (which is O(n) itself).

- DaveX December 03, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes I understand, I missed it..
But I can't seem to think of any other way..
2 loops are needed one to loop through the string the other to find the match,even if the match finding function is user defined
please, If you find an answer kindly attach a reply here

- PeyarTheriyaa December 04, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

IN PYHTON

s=input("enter string :")
s=s.replace(" ","")
size=len(s)
for i in range(0,size):
print("S(",i+1,"size) = ",s[i:])
for i in range(0,size):
r=s[i:]
count=0
for q,j in zip(r,s):
if(q == j):
count=count+1
print("len(LCP(s(",i+1,"size),s)) = ",count)

- sri December 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

s=input("enter string :")
s=s.replace(" ","")
size=len(s)
for i in range(0,size):
print("S(",i+1,"size) = ",s[i:])
for i in range(0,size):
r=s[i:]
count=0
for q,j in zip(r,s):
if(q == j):
count=count+1
print("len(LCP(s(",i+1,"size),s)) = ",count)

- SRI December 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C

#include <stdio.h>
#include <memory.h>

#define MAX_STRING 256

int main() {
    char s[] ="ababac";
    int lcps[MAX_STRING];

    for (int i=0; i<strlen(s); i++) {
        lcps[i] = 0;

        if (s[i] == s[0]) {
            lcps[i]++;
        }

        for (int j=0; j<i; j++) {
            if (lcps[j] == i && s[i] == s[lcps[j]]) {
                lcps[j]++;
            } else if (lcps[j] > 0) {
                if(s[i] == s[lcps[j]] && (j+lcps[j]) >= i) {
                    lcps[j]++;
                }
            }
        }
    }

    for(int i = 0; i < strlen(s); i++) {
        printf("len(LCP(s(%d,%d),s)) = %d\n", i, strlen(s), lcps[i]);
    }
    return 0;
}

- AF December 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C

#include <stdio.h>
#include <memory.h>

#define MAX_STRING 256

int main() {
    char s[] ="ababac";
    int lcps[MAX_STRING];

    for (int i=0; i<strlen(s); i++) {
        lcps[i] = 0;

        if (s[i] == s[0]) {
            lcps[i]++;
        }

        for (int j=0; j<i; j++) {
            if (lcps[j] == i && s[i] == s[lcps[j]]) {
                lcps[j]++;
            } else if (lcps[j] > 0) {
                if(s[i] == s[lcps[j]] && (j+lcps[j]) >= i) {
                    lcps[j]++;
                }
            }
        }
    }

    for(int i = 0; i < strlen(s); i++) {
        printf("len(LCP(s(%d,%d),s)) = %d\n", i, strlen(s), lcps[i]);
    }
    return 0;
}

- AF December 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The algorithm is pretty much to take the substrings of the main string (prefixes) and use two pointers to scan the two strings and move them at the same time until the characters do not match. I present a concise solution in Python below.

def lcpOfAllSubstrings(s):
  for i in range(len(s)):
    count = 0
    for l1, l2 in zip(s, s[i:]):
      if l1 != l2:
        break
      count += 1
    print('{}: len(LCP(s({}, {}), s)) = {}'.format(i + 1, i + 1, len(s), count))

# Test code
lcpOfAllSubstrings("ababac")

Output

1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

- prudent_programmer December 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String helper(String s1, String s2) {
    StringBuilder sb = new StringBuilder();
    int mLen = min(s1.length(), s2.length());
    for (int i = 0; < mLen; i++) {
        if(s1.charAt(i) != s2.charAt(i)) {
            break;
        }
        sb.append(i);
   }
   return sb.toString();
}

public String LPS(String arr[], int low, int high) {
    if(low == high) return arr[low];
    if(high > low) {
        int mid = low + (high - low) / 2;
        String s1 = LPS(arr, low, mid);
        String s2 = LPS(arr, mid + 1, high);
	return (helper(s1, s2));
    }
    return null;
}

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

public String helper(String s1, String s2) {

    StringBuilder sb = new StringBuilder();
    int mLen = min(s1.length(), s2.length());
    for (int i = 0; < mLen; i++) {
        if(s1.charAt(i) != s2.charAt(i)) {
            break;
        }
        sb.append(i);
   }
   return sb.toString();
}

public String LPS(String arr[], int low, int high) {
    if(low == high) return arr[low];
    if(high > low) {
        int mid = low + (high - low) / 2;
        String s1 = LPS(arr, low, mid);
        String s2 = LPS(arr, mid + 1, high);
	return (helper(s1, s2));
    }
    return null;
}

- jsdude December 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nlog(n) ?

- p.andrey January 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution in Go. I'm not convinced it's actually O(n) time though. I think it ends up being O(kn) where k is the average length of a substring (excluding s being a substring of itself).

That's because on each loop through, on average it loops through 'k' candidates to check for progress in my solution.

I don't know how you'd do this in O(n); none of the current solutions appear to be that efficient.

package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	s := "ababac"
	result := LongestPrefixesFrom(s)
	fmt.Println(FormatResult(s, result))
}

// Takes a string. Returns a map from start index to length for substrings of s
// that are also prefixes of s.
func LongestPrefixesFrom(s string) map[int]int {
	// HashMap of strings from their start point to length that are not ongoing
	// in our current scan.
	// Pre-insert 's' since it's always a substring of itself of length s
	res := map[int]int{
		0: len(s),
	}
	// HashSet of candidate. As we move through indexes, each candidate in this
	// set is valid for index i-1, starting at the index recorded in the hashset.
	// That is to say, with the example string 'ababc', the hashset might contain
	// '2' to indicate a valid substring starts at index '2'.
	// On the next index, 3, it would be checked this substring is still valid by
	// checking if the value at index 3 (1 away from the start of 2) matches the
	// value 1 from the start.
	// In this example it does match. The check will repeat at index 4 (2 away
	// from the start at index 2). Since the value at index 2 doesn't match, that
	// means the last valid character in the substring was the previous one, so
	// it can now be removed from the currently tracked substrings and moved into
	// the result set.
	candidates := map[int]struct{}{}
	for i := 0; i < len(s); i++ {
		for candidate := range candidates {
			// candidate is something like 'index 5' indicating that a prefix of s starts at 5.
			// To check if this candidate is still valid from 5 to i, we just check
			if s[i-candidate] != s[i] {
				delete(candidates, candidate)
				res[candidate] = i - candidate
			}
		}
		if s[0] == s[i] {
			candidates[i] = struct{}{}
		} else {
			res[i] = 0
		}
	}
	// add any existing candidates; those run until the end of the string
	for candidate := range candidates {
		res[candidate] = len(s) - candidate
	}

	return res
}

func FormatResult(s string, res map[int]int) string {
	parts := []string{}
	for key, val := range res {
		// +1 for 1 index instead of 0 index to match the question
		str := fmt.Sprintf("len(LCP(s(%v,%v)) = %v", key+1, len(s), val)
		parts = append(parts, str)
	}
	// sort because map iteration is random in go
	sort.Strings(parts)
	return strings.Join(parts, "\n")
}

- DaveX December 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi DaveX, could we maybe try to use a Trie for this situation?. Like insert the word "ababac" and just take substrings of it by walking down the trie? I could be wrong, but wouldn't it be O(n) time then? What are your thoughts?

- prudent_programmer December 04, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let's say you have the worst case string, which is "aaaaa...".

Your trie is now just "a -> a -> a -> a ..." (which is identical your list of "a"s really).

Let's look at the runtime of lookups in that trie: To lookup the first character, you walk n characters in the trie. For the second, you walk n-1 characters, then n-2, n-3, etc.

That ends up being the sum of 0..n, which is O(n^2).

I don't think a trie is actually any more efficient than searching the list itself because there's only one prefix to search, not a bunch, and tries only really help if there are a bunch of prefixes.

- DaveX December 04, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the given string is only one string and we need to find the common prefix of its own sub strings. Would it mean only one char or none? like only ex: aaaaa will get 1. abcde will get 0. we just need to check if all chars are same or not..

- sheshu December 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python3

inp = 'ababac'
sdict = {}

for i in range(len(inp)):
sdict[i] = inp[i:]

count = 0
LCP = {}

for sub_s in sdict.values():
for i in range(1,len(sub_s)+1):
if sub_s[:i] == inp:
LCP[sub_s] = len(inp)
count = 0
break
elif inp.startswith(sub_s[:i]):
count += 1
else:
LCP[sub_s] = count
count = 0
break


for key,value in LCP.items():
print('{}: {}'.format(key,value))

- jkatzwhitew December 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
class subseq
{
    public static void main(String[] args) 
    {
        String Sen="ababac";
        sseq(Sen);

    }

    public static void sseq(String S)
    {
        int length = S.length();
        String[] seq = new String[length];
        int values[]=new int[length];
        int l1=0;
        String s="";
        int count=0;
        int c=0;
        for(int i=0;i<length;i++)
        {
            seq[i]=S.substring(i,length);
        }
        for(int i=0;i<length;i++)
        {
            s=seq[i];
            l1=s.length();
            count=0;
            for(int j=0;j<l1;j++)
            {
                if(s.charAt(j)==S.charAt(j))
                {
                    count=count+1;
                }
                else
                {
                    break;
                }
            }
            values[c++]=count;

        }

        for(int i=0;i<values.length;i++)
        {
            System.out.println(seq[i]+"::"+values[i]);
        }
    }
}

- RIJU December 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Insert all strings into trie and then traverse from root down, the LCP is the string formed from root to the the first node with multiple children.

- Ravan January 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Insert all strings into trie and then traverse from root down, the LCP is the string formed from root to the the first node with multiple children.

- ravan January 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm a veteran, but it made me think a bit of this problem that at first glance can not be done in O (n), yet ...
So, the good news is that it can be done in O(n)... the bad news is that I would not have passed the interview :)), because it took me a while. Today I had a little time and find this idea using KMP. The idea came from the following statement: "the longest prefix which is a good suffix"... exactly what we need.

So, here are the steps:
1. Do the lps table (this is done in O(n) - see KMP algorithm), plus set the oldest parent for each suffix.
2. Rotate all ascending sub-arrays in the lps table ( O(n) )
3. If the parent for a chr is not 0 then set the lps[chr] = 0 (also done in O(n) ) and for the first char set len(s) - the longest
So, as you can see you need 3 traversal for the initial string no matter how long it is (how big is n)... thus O(3n) = O(n)

Here is an example:
step 1:
s      = a b a b a c
lps    = 0 0 1 2 3 0
parent = 0 1 0 1 0 6
- this is done in O(n)

step 2:
s      = a b a b a c
lps    = 0 0 3 2 1 0
parent = 0 1 0 1 0 6

step 3:
s      = a b a b a c
lps    = 6 0 3 0 1 0
parent = 0 1 0 1 0 6
Done.

- p.andrey January 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So, here is the implementation in python:

"""
Problem:
--------
Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n) 

For example 

s = 'ababac' 

Then substrings are as follow: 

1: s(1, 6) = ababac 
2: s(2, 6) = babac 
3: s(3, 6) = abac 
4: s(4, 6) = bac 
5: s(5, 6) = ac 
6: s(6, 6) = c 

Now, The lengths of LCP of all substrings are as follow 

1: len(LCP(s(1, 6), s)) = 6 
2: len(LCP(s(2, 6), s)) = 0 
3: len(LCP(s(3, 6), s)) = 3 
4: len(LCP(s(4, 6), s)) = 0 
5: len(LCP(s(5, 6), s)) = 1 
6: len(LCP(s(6, 6), s)) = 0 
"""
class LCP:
	@staticmethod
	def build_lps_asc_parent_tables(p:str):
		lps = [0] * len(p)
		asc = [-1] * len(p)
		parent = [i for i in range(0, len(p))]
		
		k = -1
		lps[0] = -1
		parent[0] = 0
		for i in range(1, len(p)):
			while (k >= 0 and p[k+1] != p[i]):
				k = lps[k]
			if p[k+1] == p[i]:
				k += 1
			
			# longest prefix which is also a suffix for p[0:i]
			lps[i] = k;
			parent[i] = parent[k]
			if (asc[i-1]<0 and k>=0):
				asc[i] = i
			elif (asc[i-1]>=0 and k>=0):
				asc[i] = asc[i-1]

		return (lps,asc,parent)

	@staticmethod
	def rotate_asc_subarr(a: list, asc:list):
		i = len(asc) - 1
		while i>=0:
			if asc[i] >= 0:
				# rotate
				end = i
				start = asc[i]
				while (start < end):
					a[start],a[end] = a[end],a[start]
					end -=1
					start +=1
				# jump to the next one
				i = asc[i] - 1
			else:
				i -= 1

	@staticmethod
	def filter_lsp(lsp, parent):
		for i in range(0, len(lsp)):
			if parent[i] != 0:
				lsp[i] = 0
			else:
				lsp[i] += 1
		lsp[0] = len(lsp)
		return lsp
			
class test:
	def do_test_1(self):
		s = "ababac"
		(lsp,asc,parent) = LCP.build_lps_asc_parent_tables(s)
		LCP.rotate_asc_subarr(lsp, asc)
		lcp = LCP.filter_lsp(lsp, parent)
		print(lcp)

t = test()
t.do_test_1()

I see that CLRS cut the string search algorithms from the last edition: KMP, Boyer-Moore, and Rabin-Karp. I also wrote a book (Blueprints of Common Algorithms: A simplified approach to the analysis and implementation of common algorithms) and I didn't include them in it... but it seems that they are needed, so I'm thinking to add them in the next editions.

- p.andrey January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create the suffix_arr -> O(n)
Sort it -> O(nlogn)
Build LCP array
max = Integer.MAX_VALUE;
LCP[0] =0;, j =1 to n ; and i =0 to n-1
for all suffix_arr element O(n-1)
match suffix_arr[i] with suffix_arr[i+1] and count the number of matching characters = count -> O(K) where k is max. number of matching characters between 2 suffixes
max = Math.max(max,count)
return max

I think the maximum time that we are reaching here is O(n).
Comments?

- lavender43 January 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#In Python
#Is this correct?

def cadena(string):
lista=[]
for i in range(len(string)):
lista.append(string[i:len(string)])

j=0
i=0
resultados=[]
while j<len(lista):
if i<len(lista[j]):
if string[i]==lista[j][i]:
i+=1
else:
j=j+1
resultados.append(i)
i=0
else:
resultados.append(i)
j=j+1
i=0

for i in range(len(string)):
print("len(LCP(s("+str(i+1)+","+str(len(string))+")s)="+str(resultados[i]))




s="ababac"
cadena(s)

- Ivan Chavez February 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this correct?

{{

def cadena(string):
lista=[]
for i in range(len(string)):
lista.append(string[i:len(string)])

j=0
i=0
resultados=[]
while j<len(lista):
if i<len(lista[j]):
if string[i]==lista[j][i]:
i+=1
else:
j=j+1
resultados.append(i)
i=0
else:
resultados.append(i)
j=j+1
i=0

for i in range(len(string)):
print("len(LCP(s("+str(i+1)+","+str(len(string))+")s)="+str(resultados[i]))




s="ababac"
cadena(s)




}}

- Ivan Chavez February 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

functions s(n, m) is actually creating suffix of a string starting at n. so solution is

1. Create suffix tree
2. Report the overlap length of all the suffixes which are overlapping with the full string suffix
3. All other suffixes have 0 overlapping prefix

- reezoo February 07, 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