Technical Question Review: Bouncing Around a Matrix

Overview

In this post, I'll walk through an approach to "bouncing" diagonally around a matrix. This is a question I received in a take home technical interview. I was presented with a challenge I hadn't seen before, and on the spot this one really stumped me. I took it as an opportunity to learn about a coding method I hadn't been exposed to before, and am writing about it here in case anyone else gets stumped and is looking for guidance.

The requirement is to write a function that takes in a matrix of ints (structured as a 2D array-of-arrays), calculates the "weight" of each array, and returns the sorted weights represented as the first element of each array. From the description, it's clear that this task can be broken down into roughly two separate problems: finding the weights, and sorting them.

Let me provide an example, which will help us understand how to calculate weights. Let's look at a matrix.

To calculate the weights of each row-array, we need to find all viable bounce paths from the first element of the row to the last element of another row. Let's look at the weight for the first row. Because it is the first row, it only has one viable bounce path: diagonal down. The weight in this instance would be 10, because 5 + 0 + 5 + 0 = 10.

Now let's consider the second row. The second row has two viable bounce paths: diagonal up, and diagonal down. Its weight would be the sum of both of those paths. In this case, it would be 30, because 4 + 1 + 6 + 1 = 12 and 4 + 9 + 4 + 1 = 18 and 12 + 18 = 30.

Implementation

getWeight

Now that we understand how to calculate the weight, let's look at implementation. There are two considerations for finding the weight of each row. The first, is finding all the bounce paths for each row. The second is actually traversing the matrix with a 'bounce'.

The first consideration is straightforward enough. The first and last rows only have one bounce path, but all other rows can bounce 'up' or bounce 'down'. That can be handled with an if/else structure. The second consideration is trickier (especially without pen, paper, or REPL!). In the code below, I've provided one way to calculate both diagonal up and diagonal down bounce paths through a matrix. This approach will return the weights as another array-of-arrays, but this one will look like a Map, where the first value of each array is the 'index' value of its row from the matrix, and the second value is the weight for that row.

From the above example, the returned weights from the code below would look like [[0, 10], [4, 30], [8, 40], [2, 20]].

const getWeights = matrix => {
  let weights = [];
  let size = matrix.length - 1;
  for (let i = 0; i <= size; i++) {
    let key = matrix[i][0];
    let weight = 0;
    for (let j = 0; j <= size; j++) {
      if (i === 0) {
        weight += matrix[j][j];
      } else if (i === size) {
        weight += matrix[size - j][j];
      } else {
        let diagonalUp = Math.abs(j - i);
        let diagonalDown = size - (Math.abs(size - (i + j)) % size);
        weight += matrix[diagonalUp][j];
        weight += matrix[diagonalDown][j];
      }
    }
    weights.push([key, weight]);
  }
  return weights;
};

sort

Once the weights are calculated, they must be sorted. I have mixed feelings about JavaScript's sort method for arrays. On the one hand, it's incredibly flexible (as you'll see below), but on the other, it can be less intuitive than some other languages' sort methods out of the box.

Remember, the input for the sort looks like [[0, 10], [4, 30], [8, 40], [2, 20]]. Weight needs to be sorted first (high => low) first. In the case that weights are equivalent, index values need to be sorted second (low => high). The sort method should return, in this instance, [8, 4, 2, 0].

For those unfamiliar with JavaScript, its sort method is an array enumerable, which takes in two arguments (the two elements to be compared). If -1 is returned by the code block, then the first item is placed before the second; if 1 is returned, then the second item is placed before the first. I've provided one approach to sorting below.

const sort = weights => {
  let results = [...weights];
  results.sort((first, second) => {
    // Compare Weights
    if (first[1] > second[1]) return -1;
    if (first[1] < second[1]) return 1;

    // Compare Keys
    if (first[0] < second[0]) return -1;
    if (first[0] > second[0]) return 1;
  });

  return results.map(result => result[0]);
};

Bringing it all together

These functions, getWeight and sort, keep the code clean by handling one job. One last function bouncingMatrix, will tie them together.

const bouncingMatrix = matrix => {
  let weights = getWeights(matrix);
  return sort(weights);
};

Conclusion

I hope this post was helpful. I've put all of this code in a GitHub repo with unit tests for all methods. If you're also interviewing for software engineering roles, I would encourage you to keep track of interview questions that stumped you, so you can learn from your mistakes and track areas where your knowledge is weakest.