A Microsoft Javascript Interview Question
Tags: challenge, javascript, codenewbie, computerscience
Published: 2020-10-07 21:13:28

Hey there. Welcome back to Code Review, a series of real coding interview challenges released every Thursday brought to you by [Coderbyte](https://coderbyte.com/), an interview prep platform that's helped over 500,000 developers land their next role. If you are just joining us, be sure to check out [last week's article](https://dev.to/coderbyte/reintroducing-code-review-with-an-interview-question-asked-at-amazon-5a89) where we introduced CodeReview and relaunched the series with our first challenge: an interview question asked at Amazon. 

## Solution to Last Week's Challenge
Last week we introduced the `arrayAddition` [challenge](https://dev.to/coderbyte/reintroducing-code-review-with-an-interview-question-asked-at-amazon-5a89). This challenge required us to write a method that would take in an array and return `true` if some combination of elements in the given array could be added to equal the maximum value found in that array. Over the past week, we saw some interesting approaches to the problem including @dbenchi's which even added a frontend visualization for [his solution](https://dev.to/dbenchi/comment/16e0o). 

Here is my approach to solving this problem using recursion to determine combinations of elements in the array: 

```javascript
function arrayAddition(arr) {
    if(arr.length <= 2) { return false }
    let sortedArr = arr.sort((a, b) => a - b);
    let target = sortedArr.pop();
    return isSum(sortedArr, target);
}

function isSum(arr, target){
    if(arr.length === 0){ return target === 0 }
    let first = arr[0];
    let rest = arr.slice(1);
    return isSum(rest, target - first) || isSum(rest, target)
}

// TEST CASES PROVIDED
console.log(arrayAddition([4, 6, 23, 10, 1, 3])); // true b/c 4 + 6 + 10 + 3 = 23 
console.log(arrayAddition([5,7,16,1,2])); // false 
console.log(arrayAddition([3,5,-1,8,12])); // true b/c 5 -1 + 8 = 12

// ADDITIONAL TEST CASES
console.log(arrayAddition([1,1,2])); // true
console.log(arrayAddition([1,1])); // false
console.log(arrayAddition([1,3])); // false
```

When trying to solve this problem, I first started with pseudocoding my plan of attack:

1. **Consider edge cases**: Because we are given the assumption that `arr` will not contain all of the same elements, we can infer that an array with less than or equal to 2 elements cannot meet the requirements. For example `arrayAddition([1,3])` and `arrayAddition([1,1])` should both return `false`.  

2. **Determine the target** Find the largest value (the target) and remove it from the array we examine to calculate the sum. In my solution, I first sorted the array in ascending order and then used `pop()` in order to mutate the array and remove the target. 

3. **Evaluate the sums using recursion** 
* **Find all combinations** of the array without the target and examine whether their sums are equal to the target. If you'd like a refresher on combinations (like I did), check out [this great video walkthrough](https://bit.ly/youtube-combinations) by Alvin from Coderbyte. We are examining combinations and not permutations of the array because we do not care about ordering of the elements. 

* I constructed a helper method `isSum` and used recursion to consider each combination that includes or excludes the `first` element in the calculated sum (current target). If the element is included, the element is subtracted from the current target. If the element is excluded, the current target remains the same. This is illustrated in the recursive calls `isSum(rest, target - first) || isSum(rest, target)`  

* For the base case, when we run out of elements to evaluate, we perform a check to see if the combination of elements subtracted from the current target equals 0. If yes, this condition should return true because it means that there is some combination of elements that add up to the max number, otherwise return false. `if(arr.length === 0){ return target === 0 }`

* Below is a diagram of the recursive calls this solution will run through when solving for `arrayAddition([3,5,-1,8,12]`. Here, our `target = 12` and `sortedArr = [-1, 3, 5, 8]`. At each stage, we make a decision to either include or exclude the current first value.  With the combination of `[-1, 5, 8]` we reach the base case of `arr.length === 0` and `-1 + 5 + 8 === 12` allowing us to return `true` in the recursive helper method `isSum` and return `true` for `arrayAddition`. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/j8ppr38eug0ilwdt5wye.jpg)

This was my approach to solving `arrayAddition`. What are your thoughts on this implementation?   

## This Week's Challenge

For this week's challenge, we're focusing on a Javascript interview question asked during a Microsoft interview which covers relevant real-world topics. The challenge requires us to write a function `foodDistribution` which takes in `arr` of numbers.  The `arr` represents the hunger level of different people ranging from 0 to 5 (where 0 means not hungry at all, 5 means very hungry). 

`arr` will also contain `N` sandwiches to give out which will range from 1 to 20. The format of the `arr` will be `[N, h1, h2, h3, ...]` where `N` represents the number of sandwiches you have and the rest of the array will represent the hunger levels of different people. Your goal is to minimize the hunger difference between each pair of people in the array using the sandwiches you have available.

**Examples:**
1. If `arr = [5, 3, 1, 2, 1]`, this means you have 5 sandwiches to give out and you can distribute them in the following order to the people: `2, 0, 1, 0`. By giving these sandwiches to the people, their hunger levels now become: `[1, 1, 1, 1]`. The difference between each pair of people is now `0`, the total is also `0`, so your method should return `0`. 
2. If `arr  = [4, 5, 2, 3, 1, 0]`, return `2` because you can distribute the sandwiches in the following order: `[3, 0, 1, 0, 0`] which makes all the hunger levels the following: `[2, 2, 2, 1, 0]`. The differences between each pair of people is now: 0, 0, 1, 1 and so your program should return the final minimized difference of 2.
3. If `arr = [5, 2, 3, 4, 5]`, return `1`
4. If `arr = [3, 2, 1, 0, 4, 1, 0]`, return `4`.

**Assumptions:**
1. You may not have to give out all, or even any, of your sandwiches to produce a minimized difference.
2. You will be given an array of at least 3 elements with the first element being the number of sandwiches and the last two elements, representing at least two people. 
3. `N` ranges from 1 to 20.
4. The hunger level of all people ranges from 0 to 5.

## How Will You Solve This Challenge? 
 
How will you solve world hunger? Just kidding :) We'd love to see the approaches you come up with. Please do share below in the comments. In the meantime, if you're looking for more interview prep or just interested in diving deeper into data structures and algorithms, check out Coderbyte's [challenge library](https://coderbyte.com/) and our [Youtube channel](https://youtube.com/c/CoderbyteDevelopers). Til next Thursday!   

Photo Credit: <span>Photo by <a href="https://unsplash.com/@nesabymakers?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">NESA by Makers</a> on <a href="https://unsplash.com/s/photos/coding-javascript?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></span>