Sum of a sublist

Question

The task:

Given a list of numbers L, implement a method sum(i, j) which returns the sum from the sublist L[i:j] (including i, excluding j).

For example, given L = [1, 2, 3, 4, 5], sum(1, 3) should return sum([2, 3]), which is 5.

You can assume that you can do some pre-processing. sum() should be optimized over the pre-processing step.

const lst = [1, 2, 3, 4, 5];

My functional solution:

const sum = (i,j) => lst
  .slice(i,j)
  .reduce((acc, x) => acc + x, 0);

console.log(sum(1,3));

My imperative solution:

function sum2(i,j) {
  let sum = 0;
  for(let k = i; k <j; k++) {
    sum += lst[k];
  }
  return sum;
}

console.log(sum2(1,3));

I didn't understand the last part of the task, why pre-processing and optimizing is needed for a simple task like summing up sub elements of a list.

Answer 1

The problem as a single call is trivial at best with the optimal solution being

const values = [1,2,3,4,5,6,7,8,9];
function sum(i,j) {
    var sum = 0;
    while(i < j) { sum += values[i++] }
    return sum;
}

Caching is impractical

The answer by Marc Rohloff suggests that caching the results is one way to do this. It has some flaws. \$O(n^2)\$ storage \$O(n^3)\$ complexity to get all possible solutions and make have sum perform at \$O(1)\$

Much in little, MIP maps

This problem is very similar to a CG problem regarding the rendering of images. To avoid small versions of a larger image looking pixelated each rendered pixel is the mean of the many pixels it represented. In other words a rendered pixel is sumPixels(a,b) / (b-a) (pixels from a to b) which is identical to this problem.

The solution was called MIP mapping (MIP is for the Latin "multum in parvo", meaning "much in little") (now more often called mipmaps)

Mipmaps work by pre processing the image, creating multiple copies, each copy is half the size of the previous image. So for a square 256pixel image you would have to create a 8 more images of 128, 64, 32, 16, 8, 4, 2, and 1 pixels (normally the maps would be limited to only a few steps)

The storage thus becomes \$O(2n)\$ and the same for the pre-processing complexity. In other words a pre-processing \$O(n)\$ storage and processing solution to the problem of summing continuous sets from a larger set.

The rendering per pixel was typically \$O(2)\$ or \$O(1)\$

Applying the MIP

In javascript we can create a function that will return a function. That means we can use closure to encapsulate the pre-processed data.

As we need the precise value for each set we can not use the CG mipmap method as it calculates a near enough approximation. To get the precise value we need a little more complexity. Its something near \$O(log(log(n))\$ per sum

First the pre-processing

We create multiple maps each half the size of the previous map. We use the results of the previous map to calculate the new map. As some map sizes can not be divided by two we need to tack on some zeros

function createSumFunction(array) {
    const mipMaps = [array];
    (function () {
        var from = array;
        while(from.length > 2) {
            let i = 0;
            const to = [];
            while(i < from.length) {
                to.push(from[i++] + (from[i] !== undefined ? from[i] : 0));
                i++;
            }
            mipMaps.push(to)
            from = to;
        }         
        mipMaps.push([from[0] + from[1]]);
    })();

    // more code to follow

Getting the sum

The inputs are i and j. (left and right)

First thing is reduce j by 1

To get the sum we start at the first map, from the left if we are at an odd position get the value to the left and add that value to a sum for the left side. For the right side we do the same but rather if we are at an even location get the value to the right and add it to the sum for the right side.

The half and round the values for i, and j and step to the next map up (half sized). If i === j get the value at i and subtract the left sum and right sum. The result is the value we are after.

The max number of steps will be \$O(log(n))\$ and the min will be \$O(1)\$

The second half of the solution returning the sum function. Note, it is missing some argument vetting, see snippet at bottom for better argument vetting.

return function(i,j) {
    j--;
    var k = 0, subL = 0, subR = 0;
    while(k < mipMaps.length) { // could also be while(true)
        const m = mipMaps[k ++];
        subL += i % 2 ? m[i - 1] : 0;
        subR += j % 2 ? 0 :  m[j + 1];
        i >>= 1;
        j >>= 1;
        if (i === j) { return mipMaps[k][i] - subL - subR }
    }
}

Solution pre \$O(n)\$ RAM/CPU and sum \$O(1)\$ RAM \$O(log(n))\$ CPU

As one function that does the pre process and returns the sum function. Add some checks to the sum input to ensure that the values i,j are not in conflict. It is assumed that they are in range. It is also assumed that the input array is more than 1 item long (or what would the point be?)

I have only tested positive values (but assume it will work for all numbers) and I have only tested for power of two array sizes, I leave that for you to work out (hint the right side may not end at an odd index)

function createSumFunction(array) {
    const mipMaps = [array];
    (()=>{ // to keep closure clean
        var from = array;
        while (from.length > 2) {
            let i = 0;
            const to = [];
            while(i < from.length) {
                to.push(from[i++] + (from[i] !== undefined ? from[i] : 0));
                i++;
            }
            mipMaps.push(to)
            from = to;
        }
        mipMaps.push([from[0] + from[1]]);
    })();
    return function(i, j) {
        var k = 0, subL = 0, subR = 0;
        if (i === j) { return NaN }
        if (j < i) { [j, i] = [i, j] }
        j--;
        if (i === j) { return mipMaps[0][i] }
        while (k < mipMaps.length) { // could also be while(true)
            const m = mipMaps[k ++];
            subL += i % 2 ? m[i - 1] : 0;
            subR += j % 2 ? 0 :  m[j + 1]; // << hint fix
            i >>= 1;
            j >>= 1;
            if (i === j) { return mipMaps[k][i] - subL - subR }
        }
    }
}
const sum = createSumFunction([1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8]);
console.log(sum(0,16));

Answer 2

If they're asking for optimization I would generally understand that they want you to improve performance over multiple calls, they also talk about pre-processing so in this case I would consider caching or pre-calculating results.

The trivial way would be to pre-calculate all the possible results.

let sums = []; 
for (let i = 0; i<lst.length; i++) {
  sums[i] = [];
  for (let j = i; j < lst.length; j++) {
    sums[i][j] = lst
            .slice(i,j)
            .reduce((acc, x) => acc + x, 0);
  }
}

const sum = (i,j) => sums[i][j];

console.log(sum(1,3));    

This is fine for a 5 element array. You are doing 5 pre-calculations. If the array had a thousand elements that would be about 500,000 calculations (and 500,000). The trick to understand here is that sum(i, j) is equal to sum2(i) - sum2(j) where sum2(x) is the sum of all elements starting at x. So you could rewrite this as:

const sums = lst.map( (v,i) => lst.slice(i).reduce((acc, x) => acc + x) );

const sum = (i,j) => sums[i] - sums[j];

console.log(sum(1,3));    

Although it is a personal preference, I would calculate the values on demand, something like this:

let   sums = []; 

const sum = (i,j) => sum2(i) - sum2(j);

const sum2 = (k) => {
  if (!sums[k] ) {
    console.log(`calculating _sum(${k})`);
    sums[k] =
          lst
            .slice(k)
            .reduce((acc, x) => acc + x, 0);
  }
  return sums[k];
}

console.log(sum(1,3));    
console.log(sum(2,3)); 

Answer 3

You may always chose an imperative way for efficiency and use a for or while loop but if you would like to remain in functional abstraction an O(n) efficient way could be;

var sum = (ar,si,ei) => ar.reduce((p,c,i) => i >= si && i < ei ? p + c : p, 0);

Answer 4

The simplest thing that comes into my mind is have a hashmap to cache sum of all the elements from position i to the end

for L = [1, 2, 3, 4, 5] the map would look like

Index | sum till end
   0  | 15
   1  | 14
   2  | 12
   3  | 9
   4  | 5

once you have this you can do something like this

public int sum(int i, int j) {
    return map.get(i) - map.get(j);
}

for example sum(1,3) is

map.get(1) = 14
map.get(3) = 9
result = 5;

Here preprocessing reduces the runtime complexity to O(1)