Range sum queries

Given an array arr of integers of size n. We need to compute the sum of elements from index i to index j. The queries consisting of i and j index values will be executed multiple times.

{1, 2, 3, 4, 5}
 0  1  2  3  4 indices
query(1, 3) => 2 + 3 + 4 = 9
query(2, 4) => 3 + 4 + 5 = 12

{5, 6, 7, 8, 9}
 0  1  2  3  4 indices
query(1, 3) => 6 + 7 + 8 = 9
query(2, 4) => 12

As a follow-up, the interviewer can transition into a light version of System & Design interview:

• How to handle updates in the array?
• How to handle multiple machines? What if data doesn’t fit into one machine?
• What if we need the possibility to add or remove a machine without impacting the others? Or can you redistribute the data?

Solution

Range sum queries without updates

Example feedback

Candidates struggle to come up with the optimal approach to this problem. Some of the candidates I asked this question to play around with running sums but fail to see that you have to subtract the upper limit from the lower limit.