Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE coding round, one algorithmic problem the whole time. The problem sounded manageable until I actually had to think through the edge cases under pressure.

Questions Asked (1)

Given an integer array, determine whether removing exactly one element can leave the remaining array with at least one pivot index (an index where the sum of all elements to its left equals the sum of all elements to its right). Return true or false.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I got the brute force out pretty quickly, O(n^2), try removing each element and recheck for a pivot.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and edge cases, then propose an efficient solution using prefix sums to track left and right sums. Explain how to check for a pivot after removing one element by considering each possible removal and using precomputed prefix sums to avoid O(n^2) time.

Pro tip: Mention that you can precompute total sum and use a single pass to check if removing the current element creates a pivot, achieving O(n) time and O(1) extra space. This shows you can optimize beyond the naive approach.

1. Clarify the problem

Confirm that the pivot index must be in the remaining array after removal, and that the removed element can be any element. Discuss edge cases like arrays of length 1 or 2.

2. Brute force approach

Explain that a naive solution would try removing each element and then check for a pivot in O(n) time, leading to O(n^2) overall. This shows you understand the baseline.

3. Optimize with prefix sums

Precompute the total sum and maintain a running left sum. For each index i, consider removing element i, then the new total sum is total - arr[i]. Check if there exists a pivot in the remaining array by using the running left sum and the new total.

4. Check pivot condition

For a candidate pivot index j (j != i), the left sum is sum of elements before j excluding i, and right sum is sum after j excluding i. Use prefix sums to compute these in O(1) and check equality.

5. Return result

If any removal and pivot combination satisfies the condition, return true; otherwise false. Discuss time and space complexity: O(n) time, O(1) space if using running sums.

Key Points to Mention

Prefix sums for efficient range sum queries
Handling removal of an element and its effect on sums
Edge cases: empty array after removal, single element, all zeros
Time complexity: O(n) with optimization, O(n^2) naive
Space complexity: O(1) extra space with running sums
Clarifying that pivot index must be in the remaining array

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