Technical Question Review: Bouncing Around a Matrix
Tags: javascript
Published: 2020-03-09 04:08:58

# 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.

![Imgur](https://i.imgur.com/tJQ8Nmj.png)

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`.

![Imgur](https://i.imgur.com/MwGxntm.png)

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`. 

![Imgur](https://i.imgur.com/H1blIBA.png)

# 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]]`.


```javascript
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. 


```javascript
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. 

```javascript
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](https://github.com/gortron/tech-challenge-questions) 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.