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

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE coding round, one algorithmic problem about range queries on parity patterns. Pretty clean problem once you see the prefix sum trick, but I spent way too long trying to brute force it before the hint clicked.

Questions Asked (1)

Given an integer array and a set of range queries [l, r], determine for each query whether the subarray has strictly alternating parity between adjacent elements. Preprocess the array so every query can be answered in O(1).

Algorithms & Data Structures

Author's notes

My first instinct was to just iterate through each query range and check adjacent pairs, which is obviously too slow when there are a lot of queries.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Preprocess the array by creating a boolean array where each index i (from 1 to n-1) indicates whether arr[i-1] and arr[i] have strictly alternating parity. Then build a prefix sum array over these booleans. For a query [l, r], check if the sum of alternating indicators from l+1 to r equals r - l, which means all adjacent pairs in the subarray alternate.

Pro tip: Clarify the indexing convention (0-based or 1-based) and handle edge cases like l == r (single element) and empty subarrays. Also, mention that the preprocessing takes O(n) time and O(n) space, and each query is O(1).

1. Understand the problem

Restate the problem: For each query [l, r], determine if every adjacent pair in the subarray has different parity. Confirm that 'strictly alternating parity' means arr[i] % 2 != arr[i+1] % 2 for all i in [l, r-1].

2. Define the alternating condition

Create a boolean array alt of length n-1, where alt[i] = true if arr[i] and arr[i+1] have different parity, for i from 0 to n-2.

3. Build prefix sums

Construct a prefix sum array pref where pref[0] = 0 and pref[i+1] = pref[i] + (alt[i] ? 1 : 0). This allows O(1) range sum queries.

4. Answer queries in O(1)

For a query [l, r] (0-based, inclusive), if l == r, return true. Otherwise, compute the number of alternating pairs in the subarray as pref[r] - pref[l]. The subarray is valid if and only if this count equals r - l.

5. Analyze complexity and edge cases

Preprocessing takes O(n) time and O(n) space. Each query is O(1). Handle edge cases: single-element subarray (always true), and ensure indices are within bounds.

Key Points to Mention

Preprocessing with a boolean array to capture alternating parity between adjacent elements.
Prefix sum array to enable O(1) range sum queries.
Condition for validity: sum of alternating indicators in [l+1, r] equals r - l.
Time complexity: O(n) preprocessing, O(1) per query; space complexity: O(n).
Edge cases: l == r (single element) returns true; empty subarray not possible.
Indexing convention: clarify 0-based or 1-based and adjust formulas accordingly.

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