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 parity-alternation range queries

Q: Answer parity-alternation range queries

This question evaluates a candidate's ability to reason about array properties and design efficient range-query processing for alternating-parity subarrays, and is commonly asked to assess algorithmic performance and scalability under large n and q.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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 even, one odd). For each query `[l, r]`, determine whether `nums[l..r]` is alternating-parity. ### Input - `nums`: array of integers - `queries`: list of `[l, r]` ### Output - An array of booleans `ans`, where `ans[j]` corresponds to query `queries[j]`. ### Constraints (typical) - `1 <= n, q <= 2*10^5` - `0 <= l <= r < n` - `|nums[i]| <= 10^9` Goal: answer all queries efficiently (faster than checking each subarray element-by-element per query).

Quick Answer: This question evaluates a candidate's ability to reason about array properties and design efficient range-query processing for alternating-parity subarrays, and is commonly asked to assess algorithmic performance and scalability under large n and q.

You are given an integer array nums and a list of queries. Each query is a pair [l, r] representing a 0-indexed inclusive subarray nums[l..r]. A subarray is called alternating-parity if every pair of adjacent elements inside it has different parity: one even and one odd. Return a boolean answer for each query indicating whether that queried subarray is alternating-parity. You should answer all queries efficiently, faster than checking every element in every queried range.

Constraints

1 <= len(nums) <= 2 * 10^5
1 <= len(queries) <= 2 * 10^5
0 <= l <= r < len(nums) for every query [l, r]
-10^9 <= nums[i] <= 10^9

Examples

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

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

Explanation: The entire array alternates odd/even/odd/even/odd, so every queried subarray is alternating-parity. A single-element range is always alternating-parity.

Input: ([4, 6, 7, 9, 10], [[0, 1], [1, 2], [1, 4], [3, 4], [2, 4]])

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

Explanation: Pairs (4,6) and (7,9) have the same parity, so any query containing one of those adjacent pairs is False.

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

Expected Output: [True]

Explanation: A subarray of length 1 has no adjacent pairs, so it is alternating-parity by definition.

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

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

Explanation: Negative numbers are handled by parity normally. The adjacent pair (-2, -4) is even-even, making ranges containing it non-alternating.

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

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

Explanation: Duplicate odd values 7 and 7 form a bad odd-odd pair, and 8 and 8 form a bad even-even pair.

Hints

Instead of checking an entire range, mark each adjacent pair as good or bad depending on whether the two numbers have the same parity.
Use a prefix sum over the bad adjacent pairs so you can count how many bad pairs exist inside any query range in O(1).

Quick Overview

This question evaluates a candidate's ability to reason about array properties and design efficient range-query processing for alternating-parity subarrays, and is commonly asked to assess algorithmic performance and scalability under large n and q.