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:
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 examplearrayAddition([1,3])
andarrayAddition([1,1])
should both returnfalse
.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.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 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 thefirst
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 callsisSum(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, ourtarget = 12
andsortedArr = [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 ofarr.length === 0
and1 + 5 + 8 === 12
allowing us to returntrue
in the recursive helper methodisSum
and returntrue
forarrayAddition
.
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 realworld 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:
 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 now0
, the total is also0
, so your method should return0
.  If
arr = [4, 5, 2, 3, 1, 0]
, return2
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.  If
arr = [5, 2, 3, 4, 5]
, return1
 If
arr = [3, 2, 1, 0, 4, 1, 0]
, return4
.
Assumptions:
 You may not have to give out all, or even any, of your sandwiches to produce a minimized difference.
 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.

N
ranges from 1 to 20.  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
Discussion (2)
The last week problem was very interesting. In my experience I have found that recursion is difficult to grasp but the solution it provides are very elegant. I like the tree diagram it made everything clicked for me. I am waiting eagerly for this weeks questions solution.
Hello,
I really like your challenges. As usual, by the time I have, I tried to give it a fast hit ðŸ˜‰.