How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Answer range queries for alternating parity subarrays

Q: Answer range queries for alternating parity subarrays

This question evaluates understanding of array manipulation, parity properties, efficient range-query processing, and preprocessing techniques for handling multiple queries.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an integer array `nums` of length `n` and `q` queries. Each query is a pair `[l, r]` (0-indexed, inclusive). A subarray `nums[l..r]` is called **alternating parity** if for every index `i` with `l < i <= r`, `nums[i]` and `nums[i-1]` have **different parity** (one is even and the other is odd). ### Task For each query `[l, r]`, determine whether `nums[l..r]` is alternating parity. Return a boolean array (or an array of `true/false` answers) of length `q`. ### Input/Output - Input: `nums`, `queries` - Output: list of booleans, one per query ### Constraints (reasonable interview assumptions) - `1 <= n, q <= 2*10^5` - Values in `nums` can be negative or positive; parity is based on `abs(nums[i]) % 2`. ### Notes - A subarray of length 0 or 1 is always alternating parity. - You should aim for near `O(n + q)` time overall.

Quick Answer: This question evaluates understanding of array manipulation, parity properties, efficient range-query processing, and preprocessing techniques for handling multiple queries.

You are given an integer array `nums` of length `n` and a list of `queries`. Each query is a pair `[l, r]` (0-indexed, inclusive). A subarray `nums[l..r]` is called **alternating parity** if for every index `i` with `l < i <= r`, `nums[i]` and `nums[i-1]` have **different parity** (one is even, the other is odd). Parity is based on `abs(nums[i]) % 2`, so negative values are handled by their absolute value. ### Task For each query `[l, r]`, return whether `nums[l..r]` is alternating parity. Return a list of booleans of length `q`, one per query. ### Notes - A subarray of length 0 or 1 is always alternating parity. - Aim for near `O(n + q)` total time — precompute once, then answer each query in O(1).

Constraints

1 <= n, q <= 2 * 10^5
Values in nums may be negative or positive; parity = abs(nums[i]) % 2
Each query [l, r] satisfies 0 <= l <= r <= n - 1
A subarray of length 0 or 1 is always alternating parity

Examples

Input: ([1, 2, 3, 4], [[0, 3], [0, 1], [1, 2]])

Expected Output: [True, True, True]

Explanation: Parities are odd, even, odd, even — fully alternating, so every queried subarray is alternating parity.

Input: ([1, 3, 2, 4], [[0, 3], [0, 1], [2, 3]])

Expected Output: [False, False, False]

Explanation: Parities are odd, odd, even, even. [0,3] has same-parity boundaries; [0,1] is 1,3 (both odd); [2,3] is 2,4 (both even) — none alternate.

Input: ([2, 4, 6, 8], [[0, 0], [0, 3], [1, 2]])

Expected Output: [True, False, False]

Explanation: All values are even. A single element [0,0] is trivially alternating; any length>=2 range has same-parity neighbors, so it is False.

Input: ([5], [[0, 0]])

Expected Output: [True]

Explanation: A single-element subarray is always alternating parity.

Input: ([-1, 2, -3, 4, -5], [[0, 4], [1, 3], [0, 0]])

Expected Output: [True, True, True]

Explanation: Parities (by abs) are odd, even, odd, even, odd — perfectly alternating, so all ranges qualify. Negatives are handled via abs(x)%2.

Input: ([1, 1, 2, 3], [[0, 3], [1, 3], [2, 3], [0, 1]])

Expected Output: [False, True, True, False]

Explanation: Parities are odd, odd, even, odd. The bad boundary is between index 0 and 1 (1,1 both odd). Ranges that avoid it ([1,3] and [2,3]) are alternating; ranges including it are not.

Input: ([10, 20, 30, 41, 52], [[0, 4], [3, 4], [0, 2]])

Expected Output: [False, True, False]

Explanation: Parities are even, even, even, odd, even. [0,4] and [0,2] contain even-even boundaries (False); [3,4] is 41(odd),52(even) which alternates (True).

Hints

Whether a whole subarray is alternating depends only on adjacent pairs. Precompute, for each adjacent pair (i-1, i), whether they have the SAME parity (a 'bad' boundary).
Build a prefix-sum of bad boundaries. A subarray [l, r] is alternating iff there is no bad boundary strictly between l and r — i.e. among indices l+1..r.
With the prefix sum, the number of bad boundaries in (l, r] is bad_prefix[r+1] - bad_prefix[l+1]; the answer is True iff that count is 0. Treat r <= l (length 0 or 1) as always True.

Quick Overview

This question evaluates understanding of array manipulation, parity properties, efficient range-query processing, and preprocessing techniques for handling multiple queries.