A Google Interview Question

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.

1. 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.
2. For parents, we'll construct: something like the following parents = { p1: [c1, ch2], p2: [c3]},

3. For children we'll have children = { c1: p1, c2: p2 }

4. 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:

1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
1 1 1 1 1

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

Comments

[David BENCHI]

I have a question: why this ["01111", "01101", "00011", "11110"] should return 3?
"01111"
"01101"
"00011"
"11110"
I can only see 2 contiguous lines of zeros: I will represent them as dots of (row, column)

• (1,1)(2,1)(3,1)
• (3,1)(3,2)(3,3)

Where is the third one?

[Cindy Tong]

@dbenchi Thanks for catching that. Typo on my end. It should be 2, I also added a 3rd scenario

• For strArr = ["110", "000", "111"], return 1.

[David BENCHI]

Thanks for the fix. However in the new example, this should return 2 not 1. Am I right?

[Cindy Tong]

Yes! LOL not my day today, appreciate you keeping me in check :) @dbenchi

[Alexandre Caruso]

lazy me:

    const strArr = ["01111", "01101", "00011", "11110"];
    let total = 0;
    let matrix = [];

    const buildMatrix = (arr) => {
        for (let i = 0; i < arr.length; i++) {
            matrix.push([]);
            let holeIndex = arr[i].split("");
            for (let j = 0; j < holeIndex.length; j++) {
                if(holeIndex[j] === "0") {
                    matrix[i].push(j);
                }
            }
        }
    }

    const count = (mat) => {
        for (let i = 0; i < mat.length; i++) {
            for (let j = 0; j < mat[i].length; j++) {
                if (mat[i][j+1]) {
                    if (mat[i][j] + 1 === mat[i][j+1]) {
                        total++;
                    }
                }
                if(mat[i+1]) {
                    if(mat[i+1].includes(mat[i][j])) {
                        total++;
                    }
                }
            }
        }   
    }

    buildMatrix(strArr);
    count(matrix);
    console.log(total, "count");    // 4 'count'

[Vidit Sarkar]

I think the expected answer of first additional example should be 3 and for third it should be 1.
Here is why.
I have shown the holes with indices (0-based indexing is used).

matrix_first = [
    "01111"
    "01101"
    "00011"
    "11110"
]
First Hole : (0, 0), (1, 0), (2, 0), (2, 1), (2, 2)
Second Hole : (1, 3)
Third Hole : (3, 4)

matrix_second = [
    "110",
    "000",
    "111"
]
First and Only Hole : (0, 2), (1, 2), (1, 1), (1, 0)

We need to keep in mind that,

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.

This is why for the first case (1, 3) is a separate hole.

[David BENCHI]

Hello,

Here again a fast try for this new challenge 😉.