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.

Find power-of-two subarrays within sum range

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

Hints

  1. Precompute prefix sums so any window sum is prefix[start+length] - prefix[start] in O(1).
  2. 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.
  3. 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.
  4. Emit results ordered by length first, then by start index, to get a stable, predictable output.

Loading coding console...