Katkat
Back

Answer parity-alternation range queries

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use prefix sums or dynamic tracking to determine if a range [L, R] consists of elements that alternate between odd and even parity in O(1) time after O(N) preprocessing.

Problem Description

Given an array of integers arr, we define a subarray as 'parity-alternating' if, for every adjacent pair of elements in the subarray, one is even and the other is odd. You are given q queries, where each query is defined by a pair of indices (L, R). For each query, return true if the subarray arr[L...R] (inclusive) is parity-alternating, and false otherwise.

Function Signature

def solve_parity_queries(arr, queries):
    # arr: List[int]
    # queries: List[Tuple[int, int]]
    # returns: List[bool]

Constraints

  • 1 <= len(arr) <= 10^5
  • 1 <= len(queries) <= 10^5
  • 0 <= L <= R < len(arr)

Examples

Example 1: Input: arr = [1, 2, 3, 4, 5], queries = [(0, 2), (0, 4), (1, 4)] Output: [True, True, True] Explanation: [1, 2, 3] alternates (O, E, O). [1, 2, 3, 4, 5] alternates. [2, 3, 4, 5] alternates.

Example 2: Input: arr = [1, 3, 5], queries = [(0, 1), (1, 2)] Output: [False, False] Explanation: [1, 3] and [3, 5] are not alternating (both are odd).

Edge Cases

  • Single element subarrays are always parity-alternating.
  • Empty arrays or queries with invalid ranges (if applicable).

Hints

Hint 1

Pre-calculate an auxiliary array where `diff[i]` is 1 if `arr[i]` and `arr[i+1]` have different parities, and 0 otherwise.

Hint 2

A subarray `[L, R]` is parity-alternating if and only if all adjacent pairs from `L` to `R-1` have different parities.

Hint 3

Use prefix sums on the auxiliary array to determine if the sum of 'different parity' indicators in the range `[L, R-1]` equals the total number of pairs `(R - L)`.

Follow-up questions

  • How would you modify your solution if the array were dynamic, meaning you need to support point updates (e.g., changing arr[i] to a new value) between queries?
  • What is the time complexity of your solution for preprocessing and for answering each query?
  • Could this problem be solved using a Disjoint Set Union (DSU) or Segment Tree approach if we define the 'alternating' property differently?