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:
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]
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 thesum
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 methodssum(array)
anddifferences(array)
to calculate these values.diffs = [2, 1, 1], sum = 4
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.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
// ADDITIONAL TEST CASES
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.
Additional examples:
- 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
Top comments (3)
Hello,
Here again a fast try for this new challenge 😉.
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?IMHO it should return false.
I will modify my code in a hour to consider this corner case[Edit]: Code fixed ;-)