A Facebook Interview Question

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

    // 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

Comments

[David BENCHI]

Hello,

Here again a fast try for this new challenge 😉.

[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?

[David BENCHI]

IMHO it should return false. I will modify my code in a hour to consider this corner case

[Edit]: Code fixed ;-)