## DEV Community is a community of 847,300 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Cindy Tong for Coderbyte

Posted on • Updated on

Hello! I hope you had a great week and that you got a chance to check out last week's Code Review challenge, where we introduced a coding interview question used by Microsoft.

## Last Week's Solution

For this challenge, we were asked to write a function `foodDistribution` that would take in an `arr` of numbers where the `arr` would contain `N` sandwiches to distrubute and various hunger levels `h1, h2, h3 ...`. Our goal is to minimize the hunger difference between each pair of people in the array using the sandwiches you have available.

When trying to solve this problem, what helped me was to walk through an example, step by step and pseudocode a plan of attack before coding. Let's walk through my approach for the scenario where `arr = [5, 3, 1, 2, 1]`.

### Pseudocode of the Approach:

1. From the given array extract the number of sandwiches `N` and the hunger levels (all of the remaining elements in the array). `N = 5, hungers = [3,1,2,1]`

2. Examine each pair of numbers and determine what the difference across each pair of values are. Store these `differences` in an array so we can calculate the `sum` of these differences. We care about the sum of the differences because we want to minimize the differences (to promote equal distribution across the hunger levels). In the below code, I've utilized helper methods `sum(array)` and `differences(array)` to calculate these values. `diffs = [2, 1, 1], sum = 4`

3. When distributing each sandwich, examine what the optimal hunger level to distribute that specific sandwich to is. Repeat this process until we either run out of sandwiches or reach a scenario where the sum of the differences in hunger levels is `0`. "Optimal" is calculated based on which combination of hunger levels with a distribution of one sandwich at a time produces the lowest sum of differences.

4. For the last step, we need to return the sum of the differences across the pairs of hunger levels after we've either distributed all of the sandwiches or reached equality by having a sum of differences equal to 0.

Walking through the example:

``````        N = 5, hungers = [3,1,2,1], diffs = [ 2, 1, 1], sumDiff = 4;

// Distribute one sandwich
N = 4;
// Possible combos
[2,1,2,1], diffs = [1,1,1], sumDiff = 3;
[3,0,2,1], diffs = [3,2,1], sumDiff = 6;
[3,1,1,1], diffs = [2,0,0], sumDiff = 2; // Optimal
[3,1,2,0], diffs = [2,1,2], sumDiff = 5;

// since sumDiff = 2 > 0 && N = 4 > 0, continue to distribute sandwiches

N = 3;
// Possible combos
[2,1,1,1], diffs = [1,0,0], sumDiff = 1; // Optimal
[3,0,1,1], diffs = [3,0,0], sumDiff = 3;
[3,1,0,1], diffs = [2,1,1], sumDiff = 4;
[3,1,1,0], diffs = [2,0,1], sumDiff = 3;

// since sumDiff = 1 > 0 && N = 3 > 0, continue to distribute sandwiches

N = 2;
// Possible combos
[1,1,1,1], diffs = [0,0,0], sumDiff = 0;// Optimal
[2,0,1,1], diffs = [2,1,0], sumDiff = 3;
[2,1,0,1]], diffs = [1,1,1], sumDiff = 3;
[2,1,1,0], diffs = [1,0,1], sumDiff = 2;

// Since sumDiff = 0, we can stop distributing sandwiches because we've reached equality across the pairs of hunger levels. By distributing 3 sandwiches we went from hunger levels of `[3,1,2,1]` to `[(3-2),1,(2-1),1] = [1,1,1,1]`.

// Return 0
``````

Javascript Solution

``````    function foodDistribution(arr) {
let N = arr.shift();
let hungers = arr;
let diffs = differences(hungers);
if (N >= diffs){ return 0 }
while (N > 0 && sum(diffs) > 0) {
let combos = [];
for (let i = 0; i < hungers.length; i++) {
let combo = hungers.slice();
combo[i]--;
combos.push(combo);
}

hungers = combos.reduce(minDiff);
N--;

diffs = differences(hungers);
}

return sum(diffs);
}

// HELPER METHODS
// Returns an array of differences across each pair
function differences(array) {
let diffs = [];

for (let i = 0; i < array.length - 1; i++) {
diffs.push(Math.abs(array[i] - array[i + 1]));
}
return diffs;
}

// Returns the sum of all values in an array (i.e. sum of all diffs)
function sum(array) {
return array.reduce((p, c) => p + c, 0);
}

// Compares two array and returns the array with the smallest sum of differences
function minDiff(arr1, arr2) {
if(sum(differences(arr1)) <= sum(differences(arr2))){
return arr1;
} else {
return arr2;
}
}

// GIVEN TEST CASES
console.log(foodDistribution([5, 3, 1, 2, 1])); // return 0 b/c you distribute 5 sandwiches as 2, 0, 1, 0, making hunger levels [1, 1, 1, 1]

console.log(foodDistribution([5, 2, 3, 4, 5])); // return 1 b/c you distribute 5 sandwiches as 2, 2, 1, 0 making hunger levels [4,5,5,5]

console.log(foodDistribution([3, 2, 1, 0, 4, 1, 0])); // return 4

console.log(foodDistribution([1, 5, 4, 1])); // return 3
console.log(foodDistribution([20, 5, 4, 1])); // return 0
console.log(foodDistribution([5, 4, 2, 5, 1, 1])); // return 1
console.log(foodDistribution([12, 5, 5, 5, 5, 5])); // return 0
``````

And that wraps up the approach I took to solving this challenge. What are your thoughts? How does this perform in terms of time and space complexity? Are there ways to improve this solution? I'd love to hear your thoughts in the comments below.

## This Week's Challenge

We are focusing on a challenge that has been asked in a Facebook interview and tests our understanding of binary trees.

This week we are asked to write a function `treeConstructor` which takes in `strArr` which is an array of strings that will contain pairs of integers in the following format: `(i1,i2)`, where `i1` represents a child node in a tree and the second integer `i2` signifies that it is the parent of `i1`.

For example: if `strArr` is `["(1,2)", "(2,4)", "(7,2)"]`, then this forms the following tree: Because this is a binary tree, the function should return `true` because a valid binary tree can be formed. If a proper binary tree cannot be formed with the integer pairs, then return `false`.

We can assume that all of the integers within the tree will be unique, which means there can only be one node in the tree with the given integer value.

• Input: `["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"]`, Output: `true`
• Input: `["(1,2)", "(1,3)"]`, Output: `false`

## What's Your Approach to Solving This Challenge?

Please share your thoughts on this challenge below. We'd love to see what solutions you come up with. In the meantime, check out our free ten-day email interview prep course you can access when you sign up for a free account at Coderbyte, an interview prep platform that's helped over 500,000 developers prepare for interviews.

See you next week!

Photo by Emile Perron on Unsplash

## Discussion (3) Cindy Tong

Hi @dbenchi ! As always nice touch on the front end, great use of semantically defined variables and love your consistency to our weekly challenges. For your solution, what happens when we have disconnected nodes? For example, if `strArr = ["(3,2)", "(4,5)" ]` should this return true or false?