Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round with a string algorithm problem. The question looked approachable at first but the constraint about handling long strings is what makes it actually hard.

Questions Asked (1)

Given a string, find the longest substring that appears more than once. If there are ties, return the one with the earliest starting position. The string can be very long, so a brute force approach won't cut it.

Algorithms & Data Structures

Author's notes

The naive O(n^2) solution is obvious but they're clearly fishing for something better.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a suffix array or suffix automaton to efficiently find the longest repeated substring in O(n log n) or O(n) time. Build the suffix array, compute the LCP array, and find the maximum LCP value; then resolve ties by choosing the earliest starting position.

Pro tip: Mention that you would clarify edge cases (e.g., overlapping occurrences, empty string) and discuss trade-offs between suffix arrays and suffix automata in terms of implementation complexity and memory usage.

1. Clarify requirements and constraints

Ask whether overlapping occurrences count, what to return if no repeated substring exists, and confirm the string length to justify the need for an efficient algorithm.

2. Choose an efficient data structure

Select a suffix array with LCP array or a suffix automaton, explaining why it handles long strings within time limits.

3. Outline the algorithm

Describe how to construct the suffix array, compute LCP values, and find the maximum LCP to identify the longest repeated substring.

4. Handle ties and edge cases

Explain how to track the earliest starting position among substrings with the same maximum length, and address cases like no repeats or multiple repeats.

5. Analyze complexity and test

State the time and space complexity (e.g., O(n log n) for suffix array) and walk through a small example to verify correctness.

Key Points to Mention

Suffix array construction (e.g., using prefix doubling) and LCP array computation (Kasai's algorithm)
Suffix automaton as an alternative with O(n) time and space
Time and space complexity trade-offs between different approaches
Handling overlapping occurrences and tie-breaking by earliest start position
Edge cases: empty string, no repeated substring, all characters same
Why brute force is inefficient (O(n^3) or O(n^2) with hashing) for very long strings

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.