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 Meta.

What role is this question designed for?

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

Find power-of-two subarrays within sum range

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find power-of-two subarrays within sum range states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an integer array nums and an integer k, find all subarrays whose length is a power of two and whose sum lies in the inclusive range [k, 2k]. Return the list of index ranges. Provide an algorithm faster than O(n^ 2). For non-negative nums, use sliding windows across candidate lengths (1, 2, 4, ...). For arrays with negative values, propose a prefix-sum plus balanced tree or hash-bucketing strategy and analyze complexity.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find power-of-two subarrays within sum range states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an integer array `nums` and an integer `k`, find all subarrays whose length is a power of two (1, 2, 4, 8, ...) and whose sum lies in the inclusive range `[k, 2k]`. Return the list of index ranges as `[start, end]` pairs (both endpoints inclusive, 0-indexed). Results must be returned ordered first by subarray length ascending (1, then 2, then 4, ...), and within the same length by start index ascending. **Approach.** A brute-force scan over all O(n) start positions and all O(log n) candidate power-of-two lengths, recomputing each window sum, costs O(n^2 log n). Precomputing a prefix-sum array lets each window sum be read in O(1), so the whole scan is O(n log n) — comfortably faster than O(n^2). The prefix-sum method works uniformly for non-negative and negative values (no sliding-window monotonicity assumption is needed), which is exactly why it is preferred when `nums` can contain negatives. **Examples.** - `nums = [1, 2, 3, 4]`, `k = 3` → `[[2, 2], [3, 3], [0, 1], [1, 2]]` (length-1 windows summing to 3 or 4, then length-2 windows summing in [3, 6]). - `nums = [4, -1, 2, 5]`, `k = 3` → `[[0, 0], [3, 3], [0, 1]]` (negative values handled correctly). - `nums = []`, `k = 1` → `[]`.

Constraints

0 <= len(nums) <= 10^5
nums[i] may be negative, zero, or positive
k may be negative, zero, or positive; the range [k, 2k] is empty when k < 0 (since then 2k < k)
Only subarray lengths that are exact powers of two (1, 2, 4, 8, ...) are considered
Index ranges are 0-indexed and inclusive on both ends

Examples

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

Expected Output: [[2, 2], [3, 3], [0, 1], [1, 2]]

Explanation: Length-1 windows: nums[2]=3 and nums[3]=4 are in [3, 6]. Length-2 windows: [0,1] sums to 3 and [1,2] sums to 5, both in [3, 6]. Length-4 window sums to 10, out of range.

Input: ([5], 5)

Expected Output: [[0, 0]]

Explanation: Single-element array; the only power-of-two length is 1, and the sum 5 lies in [5, 10].

Input: ([], 1)

Expected Output: []

Explanation: Empty array has no subarrays.

Input: ([1, 1, 1, 1], 10)

Expected Output: []

Explanation: No power-of-two window (lengths 1, 2, 4) sums to at least 10.

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

Expected Output: [[2, 2], [2, 3], [0, 3]]

Explanation: Length-1: nums[2]=3 in [3,6]. Length-2: [2,3] sums to 4 in [3,6]. Length-4: whole array sums to 5 in [3,6]. Demonstrates correct handling of a negative element.

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

Expected Output: [[0, 0], [3, 3], [0, 1]]

Explanation: Length-1: nums[0]=4 and nums[3]=5 in [3,6]. Length-2: [0,1] sums to 3 in [3,6]; [1,2] sums to 1 and [2,3] sums to 7, both excluded. Length-4 sums to 10, excluded.

Hints

Precompute prefix sums so any window sum is prefix[start+length] - prefix[start] in O(1).
The only candidate lengths are powers of two; there are at most floor(log2(n)) + 1 of them, so iterate length = 1, 2, 4, ... up to n.
For each length, slide the start from 0 to n - length and test whether the window sum falls in [k, 2k]. This handles negative values naturally — no monotonic sliding-window trick is required.
Emit results ordered by length first, then by start index, to get a stable, predictable output.

Quick Overview