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 thechild
andparent
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
Top comments (7)
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)
Where is the third one?
@dbenchi Thanks for catching that. Typo on my end. It should be 2, I also added a 3rd scenario
strArr = ["110", "000", "111"]
, return 1.Thanks for the fix. However in the new example, this should return 2 not 1. Am I right?
Yes! LOL not my day today, appreciate you keeping me in check :) @dbenchi
lazy me:
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).
We need to keep in mind that,
This is why for the first case
(1, 3)
is a separate hole.Hello,
Here again a fast try for this new challenge 😉.