Katkat
Back

Find power-of-two subarrays within sum range

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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