Optimizing Data Retrieval | Dataford Interview Questions

A Zensar delivery analytics pipeline stores events sorted by timestamp. Each event contains a timestamp and its payload size in bytes. Given many time-range retrieval requests, return the total payload size of events whose timestamps fall within each inclusive range.

The dataset is already sorted by timestamp. Design an efficient function that avoids scanning the full dataset for every request.

Formal Specification

Implement range_payload_totals(events, queries).

events is a list of [timestamp, payload_size] pairs sorted in nondecreasing timestamp order.
queries is a list of [start_time, end_time] pairs.
For each query, return the sum of payload sizes for events satisfying start_time <= timestamp <= end_time.
Return one integer per query, preserving query order.
An empty matching range contributes 0.

Constraints

1 <= len(events) <= 2 * 10^5
1 <= len(queries) <= 2 * 10^5
0 <= timestamp, payload_size <= 10^9
events is sorted by nondecreasing timestamp
start_time <= end_time for every query
Each query answer fits in a signed 64-bit integer

Function Signature

def range_payload_totals(events, queries):

Your question is Optimizing Data Retrieval. Start with the requirements in the Question tab.

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

Problem