webdev: (Default)
[personal profile] webdev
Continuing through the interview questions, here's another very common one: Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers inside the rectangle.

My usual way of visualizing two-dimensional matrices is as an array of arrays, thus:
var M = [];
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);
M.push([47, 63, 33,  1, 42, 46,  6, 70, 98, 93]);
M.push([36, 62, 50, 21, 92, 27, 60, 29, 15, 34]);
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);
M.push([47, 63, 33,  1, 42, 46,  6, 70, 98, 93]);
M.push([36, 62, 50, 21, 92, 27, 60, 29, 15, 34]);
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);
M.push([47, 63, 33,  1, 42, 46,  6, 70, 98, 93]);
M.push([36, 62, 50, 21, 92, 27, 60, 29, 15, 34]);
M.push([70, 37, 23, 57, 27, 22, 90, 99, 22, 59]);

Here I am taking obvious advantage of copy-and-paste! This results in a two-dimensional array (so M[9][9] = 59) but it's easier to visualize the iterations as dealing with subarrays. So the brute force solution involves adding up the subarrays from given starting points to given ending points:
function arrSum(fromRow, toRow, fromCol, toCol) {
    var totSum = 0;
    for (i = fromRow; i <= toRow; i ++) {
      var currArrSeg = M[i],
          rowSum = 0;

      for (j = fromCol; j <= toCol; j++) {
        rowSum += currArrSeg[j];
      }
      totSum += rowSum;
    }
    return totSum;
}

Arden mentions that the complexity of this solution is O(MN). That's about as good as it gets for a one-shot method. If, however, we assume that our method will be called multiple times, then this problem becomes one that can benefit from caching.

Arden discusses the caching algorithm in his original post so I won't repeat that here. In our case we'll use an object as a cache that we'll need to initialize on the first pass and use from that point on. We'll also use our arrSum method to do the initial caching, since we already have it built:
var cache = new Object();
cache.boolInitialized = false;

function optimalSolution(fromRow, toRow, fromCol, toCol) {
    if (!cache.boolInitialized) {
        var maxRow = 10,
            maxCol = 10,
            i = 0,
            j = 0;
            cache.boolInitialized = true;

        for (i = 0; i < maxRow; i++) {
            for (j = 0; j < maxCol; j++) {
                var cachePtr = i + "," + j;
                cache[cachePtr] = arrSum(0, i, 0, j);
            }
        }
    }

    var returnVal = 0,
        toRowToCol = (typeof(toRowToCol) === "undefined") ? cache[toRow + "," + toCol] : 0,
        fromRowToCol = (typeof(fromRowToCol) === "undefined") ? cache[(fromRow-1) + "," + toCol] : 0,
        toRowFromCol = (typeof(toRowFromCol) === "undefined") ? cache[toRow + "," + (fromCol-1)] : 0,
        fromRowFromCol = (typeof(fromRowFromCol) === "undefined") ? cache[(fromRow-1) + "," + (fromCol-1)] : 0;

    returnVal = toRowToCol - fromRowToCol - toRowFromCol + fromRowFromCol;
    return returnVal;
}

Now the first time we call our optimal solution it will fill the cache, and from that point it will use the cache rather than recalculating anything. So the complexity of the initial call is O(MN) but subsequent calls are O(1), which is a significant saving.

I'm using a simple object as the cache; the key is the toRow,toCol string and the value is the sum of the region. To account for occasionally looking for something in the cache that isn't there (imagine looking in the cache for the sum of 0,0 to 2,2, for example), we check for undefined values and substitute 0 for them.
From:
Anonymous (will be screened)
OpenID (will be screened if not validated)
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org


 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

webdev: (Default)
Jon Reid

October 2013

S M T W T F S
  12 345
6789101112
13141516171819
20212223242526
272829 3031  

Links