Forem: Cindy Tong

A Google Interview Question

Cindy Tong — Thu, 22 Oct 2020 13:46:48 +0000

Welcome back to Code Review. If you're just joining us, learn more about Coderbyte's weekly coding challenges and solve our first challenge here.

I hope everyone had a great week (and have made plans to vote). Let's jump right into the solution from last week's challenge which featured a Facebook interview question.

Last Week's Challenge

For the treeConstructor challenge we were asked to write a function which takes in an array containing strings that each have 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. Our goal is to return true if the values can form a binary tree, and return false if not. If you'd like to see how your solution compares with over 500,000 other users, visit the challenge page at Coderbyte here.

Last Week's Solution

Before coding let's do a quick review of what a binary tree is. If you need a more thorough review, check out our video series on trees here. To understand what a binary tree is, we must first define what a tree is. A tree is a collection of nodes where:

Condition 1 There is one root node (or one parent node).

Condition 2 There is only a single path between any two nodes (every child node has one parent node).

A Binary Tree is a special type of tree where:

Condition 3 Each node in the tree has at most two children. This means that a node can have none, one or two children.

Screenshot from our youtube video series on Trees

Now that we know what a binary tree is, let's pseudocode an approach to how we would solve this problem.

Because we will need a way to separate children from parents so we can check the above conditions, we can create hash tables where we store the parent:child and child:parent relationships.
For parents, we'll construct: something like the following parents = { p1: [c1, ch2], p2: [c3]},
For children we'll have children = { c1: p1, c2: p2 }
Then we'll need to iterate across the array of strings and for each string combo:

Parse the string "(child, parent)" so that we can easily work with the child and parent by using semantic variables.
Check if the current parent already exists in the parents hash. If it does, add the child to the array. If not, create a new array with the child in it. If the length of the array children for the current parent is longer than 2, then we violate condition 3 and should return false.
If the current child already exists in the children hash, return false since we violate condition 2 (the child has more than one parent). Otherwise, add the child and corresponding parent to the children hash.
Check condition 1 holds true by ensuring that there is only one root node (one node without a parent).

function treeConstructor(strArr) {
    let parents = {};
    let children = {};

    for (let i = 0; i < strArr.length; i++) {
        // i.e. ("1,2") => ["1", "2"]
        let pair = strArr[i].replace(/[()]/g, "").split(",");
        let child = pair[0];
        let parent = pair[1];

        //  check parents have at most 2 children 
        if (parents[parent]) {
            parents[parent].push(child);
        } else {
            parents[parent] = [child];
        }

        if (parents[parent].length > 2) {
            return false;
        }

        // check child has one parent 
        if (children[child]) {
            return false;
        } else {
            children[child] = parent;
        }
    }
    // check there is only one root node 
        let root_count = 0;
        let parent_values = Object.keys(parents)
        for(let i = 0; i < parent_values.length; i++){
            if(!children[parent_values[i]]){
                root_count += 1;
            }
            if(root_count > 1){
                return false;
            }
        }
    return true;
}

// Given test cases 
console.log(treeConstructor(["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"])) // return true 

console.log(treeConstructor(["(1,2)", "(1,3)"])) // return false since we have a child with more than 1 parent

// Additional test cases 
console.log(treeConstructor(["(1,2)", "(3,2)", "(4,2)"])) // return false since we have a parent with more than 2 children 
console.log(treeConstructor(["(3,2)", "(4,5)" ])) // return false where we have disconnected nodes (more than 1 parent)

That's my approach to solving Tree Constructor. If I were solving this problem in a live interview, what I like about my appraoch is that I started first with the conditions that needed to hold true for us to construct a valid binary tree and then solved for these scenarios one at a time without trying to solve for everything at once. This made the problem much more approachable for me. Nevertheless, there are ways we can optimize this solution. What do you think we could improve?

This week's challenge

We have a challenge used during a Google interview that requires us to work with matrices (something I was horried of when I first started solving algorithmic questions).

For this week's challenge, we are asked to write a function bitmapHoles that takes in strArr which is an array of strings that form a 2D matrix of 0 and 1's. The function should determine how many holes, or contiguous regions of 0's, exist in the matrix. A contiguous region is one where there is a connected group of 0's going in one or more of four directions: up, down, left, or right.

Example 1
If strArr is ["10111", "10101", "11101", "11111"], then this looks like the following matrix:

For the input above, your function should return 2 because there are two separate contiguous regions of 0's, which create "holes" in the matrix.

Additional Examples

For strArr = ["01111", "01101", "00011", "11110"], return 2.
For strArr = ["1011", "0010"], return 2.
For strArr = ["110", "000", "111"], return 2.

You can assume that input strArr will not be empty.

How will you solve this challenge?

I'd love to see how you would approach solving this problem. If you have any tips on future challenges you'd like us to cover during Code Review, feel free to comment below. If you're looking for more interview prep tips and learning tools, check out Coderbyte. See you next week!

Photo by Johannes Plenio on Unsplash

A Facebook Interview Question

Cindy Tong — Thu, 15 Oct 2020 16:49:28 +0000

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

A Microsoft Javascript Interview Question

Cindy Tong — Wed, 07 Oct 2020 21:13:28 +0000

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 example arrayAddition([1,3]) and arrayAddition([1,1]) should both return false.
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 the first 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 calls isSum(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, our target = 12 and sortedArr = [-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 of arr.length === 0 and -1 + 5 + 8 === 12 allowing us to return true in the recursive helper method isSum and return true for arrayAddition.

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 real-world 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 now 0, the total is also 0, so your method should return 0.
If arr = [4, 5, 2, 3, 1, 0], return 2 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], return 1
If arr = [3, 2, 1, 0, 4, 1, 0], return 4.

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

Reintroducing Code Review with an Interview Question Asked at Amazon

Cindy Tong — Thu, 01 Oct 2020 13:53:49 +0000

Reintroducing Code Review

Hi there! I’m Cindy from Coderbyte, an online developer interview prep and learning platform. In celebration of Coderbyte reaching 500,000 developers, we’re relaunching our weekly code challenge series: Code Review. Every Thursday, we’ll launch a new coding challenge used in a real interview for free to Dev.to. Readers can submit their solutions in the comments section of each article for the opportunity to have their code reviewed by Codebyte and our readers. Let’s jump directly to this week’s challenge.

The Challenge

This week we’re focusing on an algorithms based question asked during an interview at Amazon. In this challenge, we’re asked to write a function ArrayAddition in Javascript that takes in an array of numbers stored in a variable named arr.

The function should return the string true if any combination of numbers in the array (excluding the largest number) can be added up to equal the largest number in the array.

Otherwise, the function should return the string false.

Examples:

If arr contains [ 4, 6, 23, 10, 1, 3 ] the output should return true because 23 is the largest number and 4 + 6 + 10 + 3 = 23.
If arr contains [ 5, 7, 16, 1, 2 ], the output should return false because none of the numbers add up to the largest number of 16.
If arr contains [ 3, 5, -1, 8, 12 ], the output should return true because 12 is the largest number and 5 + 8 - 1 = 12.

Some assumptions we can make:

The arr will not be empty.
The arr will not contain all the same elements but can contain some duplicate elements. For instance, the array cannot be [ 2, 2 ], however, it can be [ 2, 2, 4 ]
The array may contain negative numbers.

Tips for Solving the Problem

Some things to consider when approaching this problem:

Are there any edge cases we have not accounted for?
How would you approach whiteboarding an approach before coding?
What would a recursive solution look like and how would it compare to an iterative approach? If you need a refresher on recursion, check out our Master Recursion Youtube series.
What is the time and space complexity of your solution? Check out our video guide on Big O for reference.

Once you have a solution that passes the test scenarios above, please share with us in the comments for a chance to be selected as this week’s winner.

More Resources

At Coderbyte, you can sign up for our free 10-day interview prep email course, access our challenge library of over one million solutions, learn through interview kits and starter courses, and practice with mock interviews. We also have more insights on career and interview prep on Medium as well as additional free video tutorials on Youtube.

About Me

I’ve worked in tech for over five years. My journey to engineering has been non-traditional. In my former lives, I’ve worked as a real estate broker, product manager, growth lead and UX designer. I’ve also taught full-stack development at App Academy, a coding bootcamp where I also learned how to code. Currently, outside of Coderbyte I work as a backend engineer at Knotch where we build a content intelligence platform used by Fortune 100 companies. My passion for making engineering careers accessible is what drew me to join the Coderbyte team. Feel free to reach out to me at cindy.tong@coderbyte.com if you have ideas on how we can improve this series.

Til Next Week

We’ll see you next Thursday where we will discuss various approaches to this problem and highlight some reader-submitted solutions.

Credits: Photo by ThisisEngineering RAEng on Unsplash