An online interview test question, any ideas?
Anonymous User
54

There's a hidden array arr, given its length n and a set of queries [L, R]. The query [L, R] means that we have already known the sum between arr[L] and arr[R] both inclusively, e.g. arr[L]+arr[L+1]+...+arr[R-1]+arr[R], return all possible indexes that we can get the corresponding value of arr. Here's an example:

If we set n = 3, queries = [[1,3], [2,2], [3,3]], then the answer should be [1,2,3]. Because from the queries, we have known the sum of arr[1]+arr[2]+arr[3], [2,2] and [3,3] means we also have known the value of arr[2] and arr[3], so we can finally get the value of arr[1].

Both the n and the number of queries satisfies: 1 <= n, the length of queries <= 10^5.

Comments (2)