A Facebook Interview Question
Tags: codenewbie, javascript, computerscience, career
Published: 2020-10-15 16:49:28

Hello! I hope you had a great week and that you got a chance to check out last week's [Code Review challenge](https://dev.to/coderbyte/a-microsoft-javascript-interview-question-solution-for-arrayaddition-4i41), 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:**
```javascript
        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**

```javascript
    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:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/q9800gc7qwoirwhwmeg2.jpg)

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](https://coderbyte.com/), an interview prep platform that's helped over 500,000 developers prepare for interviews.  

See you next week! 


<span>Photo by <a href="https://unsplash.com/@emilep?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Emile Perron</a> on <a href="https://unsplash.com/s/photos/coding?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></span>