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


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