Dataford
Interview QuestionsInterview GuidesExperiencesMock InterviewsPricing
Get started

Prefix Sum for Range/Subarray

EasyPython00:00
Practice interviewer
In session
5 left
00:00

Your question is Prefix Sum for Range/Subarray. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Supermicro monitoring software stores integer telemetry readings in chronological order. Given the readings and many inclusive range queries, return the sum of each requested range efficiently.

Build a prefix-sum array so that each query can be answered without scanning every element in its range.

Formal Specification

Implement range_sum_queries(nums, queries).

  • nums is a list of integers, where nums[i] is the reading at index i.
  • queries is a list of two-element lists [left, right] with inclusive, zero-based bounds.
  • Return a list of integers where the result at position k is the sum of nums[left:right + 1] for queries[k].
  • The input array is not modified.

Constraints

  • 1 <= nums.length <= 100,000
  • 1 <= queries.length <= 100,000
  • -10^9 <= nums[i] <= 10^9
  • 0 <= left <= right < nums.length
  • Each query uses inclusive, zero-based indices

Function Signature

def range_sum_queries(nums, queries):
Your solutionPython 3
You need to log in / sign up to run or submit.
Run your code to see test output