Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Google SWE interview with a range query problem that looked simple on the surface but had a neat preprocessing trick behind it. Pretty clean problem once you see the pattern.

Questions Asked (1)

Given an array of integers and a set of range queries [l, r], determine for each query whether the subarray from index l to r alternates between odd and even values at every adjacent pair. Solve with O(n) preprocessing and O(1) per query.

Algorithms & Data Structures

Author's notes

The brute force is obvious and they'd probably let you code it, but the real question is whether you see the prefix sum angle.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Preprocess the array to create a prefix array where each element indicates whether the adjacent pair ending at that index alternates (i.e., has different parity). Then, for each query [l, r], check if the sum of alternating indicators from l+1 to r equals r - l, which means every adjacent pair in the subarray alternates. This yields O(n) preprocessing and O(1) per query.

Pro tip: Clarify that the alternating condition is about parity (odd/even), not value, and mention that the prefix sum approach works because the condition is monotonic and can be aggregated. Also, handle edge cases like l == r (single element) which trivially alternates.

1. Understand the problem

Clarify that a subarray alternates if for every i from l to r-1, arr[i] and arr[i+1] have different parity (one odd, one even). Confirm that a single-element subarray always satisfies the condition.

2. Design preprocessing

Create an array alt of size n-1 where alt[i] = 1 if arr[i] and arr[i+1] have different parity, else 0. Then build a prefix sum array pref where pref[i] = sum of alt[0..i-1] (with pref[0]=0).

3. Answer queries in O(1)

For a query [l, r], if l == r, answer true. Otherwise, compute the number of alternating adjacent pairs in the subarray as pref[r] - pref[l] (using 0-indexed arrays and adjusting indices appropriately). If this count equals r - l, then every adjacent pair alternates, so answer true; else false.

4. Analyze complexity

Preprocessing takes O(n) time and O(n) space. Each query is answered in O(1) time. This meets the required constraints.

5. Test with examples

Walk through a small example, such as arr = [1,2,3,4] and queries [0,3] (alternates? 1-2 yes, 2-3 yes, 3-4 yes => true) and [0,2] (1-2 yes, 2-3 yes => true). Also test a non-alternating case like arr = [1,3,2] and query [0,2] (1-3 no => false).

Key Points to Mention

Parity check: (arr[i] % 2) != (arr[i+1] % 2) or (arr[i] + arr[i+1]) % 2 == 1.
Prefix sum array to count alternating adjacent pairs.
Condition for a subarray to alternate: number of alternating pairs equals length-1.
Edge case: single-element subarray always alternates.
Time complexity: O(n) preprocessing, O(1) per query.
Space complexity: O(n) for the prefix array.

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