A Microsoft Javascript Interview Question

Hey there. Welcome back to Code Review, a series of real coding interview challenges released every Thursday brought to you by Coderbyte, 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 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. 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.

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

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

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

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 and our Youtube channel. Til next Thursday!

Photo Credit: Photo by NESA by Makers on Unsplash