Advertisement Click Range Sums
Google● EasyINTERNONSITE INTERVIEWProblem statement
You are given an integer array clicks, where clicks[i] is the number of advertisement clicks recorded in time bucket i, and an array queries of range queries.
Each query is a two-element array [left, right] describing a zero-based, inclusive range. Return a long[] whose value at index j is the total number of clicks from queries[j][0] through queries[j][1]. Preserve the input query order.
Interview extensions
- Explain how the design would change if the click array supported point updates between range-sum queries.
- Explain how a streaming consumer could process millions of queries without retaining the entire query batch or answer batch in memory.
Function
rangeClickSums(clicks: int[], queries: int[][]) → long[]Examples
Example 1
clicks = [3,0,2,5,1]queries = [[0,2],[1,3],[3,4]]return = [5,7,6]The three inclusive totals are 3 + 0 + 2 = 5, 0 + 2 + 5 = 7, and 5 + 1 = 6.
Example 2
clicks = [4]queries = [[0,0]]return = [4]The only query covers the single time bucket, so its total is 4.
Example 3
clicks = [0,0,0]queries = [[0,2],[1,1]]return = [0,0]Every bucket contains zero clicks, so every queried total is 0.
Example 4
clicks = [1000000000,1000000000,1000000000]queries = [[0,2],[1,2]]return = [3000000000,2000000000]The totals exceed the int range, so they are returned as long values.
Constraints
1 <= clicks.length <= 2000000 <= clicks[i] <= 10^91 <= queries.length <= 200000- Each
queries[j]contains exactly two integers[left, right]. 0 <= left <= right < clicks.length- Range totals may exceed the
intrange, so return them aslongvalues.