Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Google SWE interview with a dynamic programming problem that had a twist I didn't see coming. The O(n) constraint is what makes this one actually interesting.

Questions Asked (1)

Given an integer array and a target value, find the indices of the longest subsequence that sums to the target. The solution must run in O(n) time.

Algorithms & Data Structures

Author's notes

The 'longest subsequence' part threw me off more than I expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: 'subsequence' typically means contiguous subarray, but if non-contiguous, the problem is NP-hard and O(n) is impossible. Assuming contiguous, use a hash map to store prefix sums and their earliest indices, then iterate through the array to find the longest subarray summing to target. This yields O(n) time and O(n) space.

Pro tip: Always state your assumptions and ask clarifying questions before diving into the solution. Mentioning the NP-hardness of the non-contiguous case shows depth and prevents you from solving the wrong problem.

1. Clarify the problem

Ask whether 'subsequence' means contiguous subarray or not. If non-contiguous, explain that the problem is NP-hard and O(n) is impossible, so assume contiguous.

2. Outline the approach

Use a hash map to store the first occurrence of each prefix sum. Iterate through the array, compute the running sum, and check if (sum - target) exists in the map to find a subarray.

3. Handle edge cases

Initialize the map with prefix sum 0 at index -1 to handle subarrays starting at index 0. Also consider empty array, no solution, and multiple solutions (track the longest).

4. Analyze complexity

Explain that the algorithm runs in O(n) time because each element is processed once, and O(n) space for the hash map.

5. Test with examples

Walk through a small example to verify correctness, such as array [1, -1, 5, -2, 3] and target 3, showing how the map updates and the longest subarray is found.

Key Points to Mention

Clarify the definition of 'subsequence' vs 'subarray' and the implications for complexity.
Use prefix sums with a hash map to achieve O(n) time.
Initialize the hash map with prefix sum 0 at index -1 to handle subarrays starting at index 0.
Track the earliest index for each prefix sum to maximize subarray length.
Consider edge cases: empty array, no solution, multiple solutions.
Time and space complexity: O(n) time, O(n) space.

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