Forem: Coderbyte

BigO for technical interviews

Daniel Borowski — Tue, 18 May 2021 01:14:57 +0000

When preparing for upcoming technical interviews (especially for software engineering roles at FAANG companies), you might practice by solving coding challenges online and preparing by solving common interview questions.

One of our previous articles lists some common platforms where you can practice coding, like:

Big-O is an important concept you'll come across when learning about algorithms and data structures.

Big-O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Coderbyte is the only platform where the runtime analysis for your solutions is generated and expressed in Big-O notation automatically in your profile. Below is a screenshot of how it'll look on your profile after solving a coding challenge.

function FindIntersection(strArr) { 
  let arr1= strArr[0].split(', ');
  let arr2 = strArr[1].split(', ');
  let intersArr= [];
  for (i = 0; i < arr1.length; i++) {
    if (arr2.includes(arr1[i])) {
      intersArr.push(arr1[i])
    }
  }
  return intersArr.toString();
}

When you submit a solution for a challenge and it passes all the test cases, your solution is then sent to our runtime-analysis server where we run a series of progressively larger test cases, and then statistically determine what runtime trajectory it matches. We currently will return one of the following common Big-O results.

We open-sourced our code for this as well (written in TypeScript) so you can learn how it works!

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

Hi CodeLand, we're Coderbyte and we're here to help you level up your interview skills.

Daniel Borowski — Thu, 23 Jul 2020 12:02:20 +0000

Coderbyte is the #1 coding challenge platform for interview prep. We offer a collection of code challenges and web development courses that can help you prepare for upcoming job interviews. The coding challenges range in difficulty and they can all be completed straight in our online editor!

We're so excited to be at Codeland, and hope we can help you level up your coding and interview skills. Check us out at Coderbyte.com and take the Codeland challenge today.

Here's what you can expect (psssst scroll down for a special CodeLand discount):

A CodeLand Exclusive Discount ✨

If you're excited about our approach to interview prep, then today's your lucky day! Please enjoy 30% off any subscriptions or crash courses with this special CodeLand link.

If you have any questions at all, please feel free to leave a comment down below :)

The Best Code Interview Prep Platforms in 2020

Daniel Borowski — Tue, 16 Jun 2020 04:55:17 +0000

Software developer interviews are rapidly evolving. Years ago, mastering data structures and common algorithms was enough to ace an interview and get a job. Today though, employers want candidates with real-world experience and skills.

That’s why many interviewers won’t even ask data structure or algorithm questions at all. Instead, they'll focus on proficiencies with full-stack technologies and collaboration skills.

Job seekers would be wise to practice code challenges and take mock interviews to make sure they’re prepared. There are countless books and resources, such as Cracking The Coding Interview, and popular online code challenge websites.

In addition to those resources, here are the best code interview prep platforms for developer candidates.

Coderbyte

Coderbyte, my website, is the only site to offer full-stack coding challenges, interview prep courses, and mock interviews. With 500+ challenges, articles, and videos across algorithm, front-end, and even database technologies, you can quickly assess and refine your skills for any role. We also showcase user-submitted and official solutions for all challenges.

Interview Cake

Frequently considered the best source for interview articles, tips, and content, Interview Cake is a crash course in getting a software development job.

They offer courses that are specific to leading technology companies, and provide guidance beyond solving coding problems, such as advice on how to effectively communicate with interviewers even when you don’t know the answer.

AlgoExpert

AlgoExpert is one of the original coding challenge websites. The site offers tons of video tutorials, certifications, and interview tips. Their interview prep includes a selection of 100 challenges across all types of technologies and roles.

Interviewing.io

Interviewing.io takes a very unique approach to coding interview prep. Rather than providing content and practice coding challenges, Interviewing.io has a library of actual video interviews that you can watch, and you can pay to anonymously take a mock interview with an engineering hiring manager.

You may still need to practice coding on another site, but this is a great investment to get actionable feedback.

Leetcode

Like Coderbyte and AlgoExpert, Leetcode is one of the original coding challenge websites. They offer many interview prep courses for tech companies and roles, and display the average scores for different cohorts of developers so you can easily benchmark.

HackerEarth

Famous for their coding competitions and hackathons, HackerEarth recently launched a feature for mock interviews.

They have a massive community of international developers and companies, so this is a great site if you are also looking to connect with a potential employer.

HackerRank

Known for their recruiting tools, HackerRank also offers code challenges and interview prep for developers. There's no premium version, so you can access their strong library of challenges for free. It’s a good place to start for a job seeker that isn’t sure yet if they are ready to invest in premium interview prep.

A unique JavaScript interview challenge

elisabethgross — Thu, 27 Feb 2020 05:01:25 +0000

What’s up team?! Welcome back to Code Review, a series of coding interview challenges and career related content released weekly exclusively on Dev.to. I’m Elisabeth Gross and you might know me from the work I do on Coderbyte, a site dedicated to helping developers of any level get their next engineering job. Or, you may have heard of me via Breadwinnerss, a tool that helps users request intros for whichever roles they're interested in across dozens of companies.

The best part about writing this series is getting to know you all as a community of driven and excited developers, passionate about leveling up their coding skills. If you want more tips and tricks along with some developer lifestyle content, give me a follow on Instagram @elisabethgross568. I’ll be posting about what coffee shops I love to work at in NYC, some of my favorite playlists to listen to while coding and more! I can’t wait to engage with you all more. Alright, enough chit chat - let’s jump into the solution for last week’s challenge.

The solution

This solution finds how much volume of water can exist in a horizontal plane and then sums each layer to get the total volume. At each horizontal level, we can find the peaks, or the bounds where water can exist between, and subtract the indices of each peak to get the space between them where water can collect. This might be easier to visualize with some code!

Pro Tip

This problem is a GREAT opportunity to build some helper functions. Often, when solving an algorithm challenge where a lot is going on, it is helpful to start with the more general concepts, stubbing in helper functions that you can work on as the interview goes on. This communicates two things to your interviewer. First, you understand the larger concept of the problem and can build a mini roadmap for yourself made up of the smaller building blocks of the puzzle that will ultimately become your algorithm. And second, you don’t get bogged down with the details. Too often when I am interviewing someone, they get caught up in a small part of the algorithm early on and we never make it to the real meat of the algorithm. Stubbing in helper functions allows you to focus on the basic structure right off the bat, and then gives you opportunity to fill in those helper functions with the time you have left.


function totalWaterVolume(arr) {

    // first, we find the 'maxHeight’ which is the highest peak in the water collector
    const maxHeight = Math.max(...arr)

    let totalVolume = 0

    // this loop starts at the maxHeight then decrements the height
    for (let horizontalLevel = maxHeight; horizontalLevel > 0; horizontalLevel--) {

        // 'peaksAtHorizontalLevel' is set to the return value of our first helper function 'peakIndicesMaker' which will be an array of indices of rain collector walls that exist at that level
        var peaksAtHeightLevel = peakIndicesMaker(arr, horizontalLevel)

        // 'vol' is then incremented by the volume that exists at that level, returned from our second helper function 'volAtLevel'
        totalVolume += volAtLevel(peaksAtHeightLevel)
    }

    // total volume is returned
    return totalVolume
}

Let’s take a look at an example to help illustrate what we have so far.

Given the array [0, 3, 0, 1, 0, 0, 0, 1, 0, 2], our rainwater collector will look like this-

First we get the maxHeight which will be 3 in our example. We’ll start looping through each horizontal level beginning with 3.

Let’s start to build out the peakIndicesMaker function! Remember, this function should return the peaks at each horizontal layer of the rain catcher.

/* This function takes the original array, as well as the height level we are looking at, and returns an array of indices where reservoir walls exist */
function peakIndicesMaker(arr, level) {

    const peakIndices = []

    // loop over the entire array
    for (let i = 0; i < arr.length; i++) {

        // if the wall height present at each index is at least the height of the given level then that index is pushed to the output array
        if(arr[i] >= level) {
            peakIndices.push(i)
        }
    }

    // array of indices is returned
    return peakIndices
}

For our example, level 3 will return [1] (just one peak at index 1), level 2 will return [1, 9] (two peaks at index 1 and 9) and level 1 will return [1, 3, 7, 9] (four peaks at index 1, 3, 7, and 9).

Getting the indices of the peaks at each level will allow us to find the space between them which will ultimately give us the volume of water that will collect there! Let’s look at how that will look in code.

/* The distance between the two walls at the same height will also be the volume of water held between them. */
function volAtLevel(peakIndices) {

    let levelVol = 0

    // if there is only one wall at the height currently being calculated, there cannot physically be any water at that level. In this case, we return 0 volume.
    if (peakIndices.length === 1) {
        return 0
    } else {

        // levelVol is incremented for each 'pair' of walls at that level. It is important to note that we are comparing each wall to its adjacent neighbor located at the next index in the array. Therefore the last element in the array could not possibly hold water to its right.  This is because no wall exists at that level beyond the last wall
        for (let i = 0; i < peakIndices.length-1; i++) {

            // Measure the right side of one wall (this is why we look at peakIndices[i] + 1 and not just peakIndices[i]) to the left side of its neighbor
            levelVol += (peakIndices[i + 1] - (peakIndices[i] + 1))

        }
    }

    // the level volume is then returned after all pairs have been summed.
    return levelVol
}

For our example, at the first horizontal level (height = 3), we return 0 because there is only one peak index.

For the next level (height = 2), we have two peaks [1, 9]. We subtract 2 (the index of the first peak plus 1) from 9 (the index of the second peak) and get 7.

For the next level (height = 1), we have 4 peaks [1, 3, 7, 9]. We subtract 2 (the index of the first peak plus 1) from 3 (the index of the second peak) and get 1. We then subtract 4 (the index of the second peak plus 1) from 7 (the index of the third peak) and get 3. And finally we subtract 8 (the index of the third peak plus 1) from 9 (the index of the fourth peak) and get 1.

The total volume will be the sum of all the volumes at each layer which in this case will be 12. And that’s it! Hope you enjoyed this problem as much as I did :) See you next week!

A fun JavaScript interview challenge

elisabethgross — Thu, 20 Feb 2020 04:48:51 +0000

My favorite part about writing this series is getting to know you all as a community of driven and excited developers, passionate about leveling up their coding skills. If you want more tips and tricks along with some developer lifestyle content, give me a follow on Instagram @elisabethgross568. I’ll be posting about what coffee shops I love to work at in NYC, some of my favorite playlists to listen to while coding and lot of other fun stuff! I can’t wait to engage with you all more. Alright, enough chit chat - lets jump into the solution for last week’s challenge.

The solution

This solution leverages the fact that anagrams will all have the same letter frequency as each other albeit in a different order. We can use an object to store what letters are in each string and how often they appear. If both strings have the same letter frequency - we have an anagram! Here’s what that looks like in code:

function anagram(str1, str2) {
  // replace all whitespace characters
  const arr1 = str1.toLowerCase().replace(/\s+/g, '').split('')
  const arr2 = str2.toLowerCase().replace(/\s+/g, '').split('')

  const obj = {}
  arr1.forEach(letter => {
    if (!obj[letter]) obj[letter] = 0
    obj[letter]++
  })
  arr2.forEach(letter => {
    if (!obj[letter]) return false
    else obj[letter]--
  })
  for (var letter in obj) {
    if (obj[letter] !== 0) return false
  }
  return true
}

Time complexity

This solution has a time complexity of O(n) because we only have to go through each string one time to build the objects that track the letter frequency. Often you can use objects to keep track of something as a great way to reduce the time complexity of an algorithm. Using objects is cheap because getting and setting keys and values has a time complexity of O(1).

This week’s challenge

You are a programmer that has decided to move out of the city and into the forest for some much needed peace and quiet. You normally get your water from a local well, but it seems to have gone dry. You’ve decided to collect rain water to filter, however, your collection device isn’t flat. Write an algorithm to determine how much rain you can possibly collect at once given n non-negative integers representing an elevation map where the width of each bar is 1.

Example: Given [0,3,0,1,0,0,0,1,0,2] return 12

This can be visualized as follows:

Enjoy!

Our newsletter 📫

We send out a small, feature reveal snippet every time we release something big, so our community is the first to know when we break out something new. Give us your email here and we'll add you to our "first to know" list :)

Exclusive Coderbyte promo

And, as a thank you to our awesome Dev.to community, we'd love to extend a special promo to our readers. Check out this secret checkout page for 30% off our subscriptions and one-time payments.

A classic interview question

elisabethgross — Wed, 05 Feb 2020 17:10:56 +0000

Hey everyone! Welcome back to Code Review, a series of coding interview challenges and career related content released weekly exclusively on Dev.to. I’m Elisabeth Gross and you might know me from the work I do on Coderbyte.com, a site dedicated to helping developers of any level get their next engineering job. Or, you may have heard of me via Breadwinnerss, a tool that helps users request intros for whichever roles they're interested in across dozens of companies. You might just be part of this awesome Dev.to community of passionate coders. Regardless of where you came from, welcome! If you like content like this - be sure to sign up for our newsletter here. Stand up’s over - lets get into the article!

The challenge

Given two strings, return true if they are anagrams of each other. Remember, an anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

The less optimal approach

The sort function

This solution takes advantage of the built in sort function that comes with the javascript language. Many languages have a sort function but it’s important to know what the sort implementation is under the hood, especially when it comes to the overall time complexity of your algorithm. The V8 engine (the engine that powers the javascript that runs in the Chrome browser and Node.js) implements array sort using the MergeSort algorithm and has a time complexity of O(nlog(n)). It’s really important to demonstrate to your interviewer that you understand that using a built in method isn’t “free”, it’s just someone else’s code :)

The solution

Once you sort the strings, you can just compare them! If they are equal, they are anagrams. If they aren’t, return false. This is relatively straightforward in code.

function anagram(str1, str2) {

  // replace all whitespace in string, split into arrays, sort and rejoin as strings
  sorted1 = str1.toLowerCase().replace(/\s+/g, '').split('').sort().join()
  sorted2 = str2.toLowerCase().replace(/\s+/g, '').split('').sort().join()

  return sorted1 === sorted2
}

Try and come up with a more optimal solution for next week. Happy coding!

A JavaScript interview question asked at Google

elisabethgross — Wed, 29 Jan 2020 20:40:15 +0000

Hello and welcome back to Code Review, a series of coding interview challenges and career related content released weekly exclusively on Dev.to. I’m Elisabeth and I’ve been a software engineer for about 4+ years now. I’m passionate about sharing my knowledge, and best tips and tricks when it comes to acing that interview and or just leveling up your coding skills. If you want more content and challenges like these, subscribe to the Coderbyte newsletter here. That’s it for stand up - let’s get to challenge solving!

The Challenge

Write a class, EventEmitter that has three methods: on, emit, and removeListener.

on("eventName", callbackFn) - a function that takes an eventName and a callbackFn, should save the callbackFn to be called when the event with eventName is emitted.
emit("eventName", data) - a function that takes an eventName and data object, should call the callbackFns associated with that event and pass them the data object.
removeListener("eventName", callbackFn) - a function that takes eventName and callbackFn, should remove that callbackFn from the event.

For example:


let superbowl = new EventEmitter()

const cheer = function (eventData) {
  console.log('RAAAAAHHHH!!!! Go ' + eventData.scoringTeam)
}

const jeer = function (eventData) {
  console.log('BOOOOOO ' + eventData.scoringTeam)
}

superbowl.on('touchdown', cheer)
superbowl.on('touchdown', jeer)

superbowl.emit('touchdown', { scoringTeam: 'Patriots' }) // Both cheer and jeer should have been called with data

superbowl.removeListener('touchdown', jeer)

superbowl.emit('touchdown', { scoringTeam: 'Seahawks' }); // Only cheer should have been called

The solution:

This is a great opportunity to use ES6 classes. In case you haven’t used them before, check out their syntax here. We can start with a basic structure for the class EventEmitter and initialize it with an object events that we will use to track our events.

class EventEmitter {
  constructor () {
    this.events = {}
  }
}

On

Next we can start working on our methods. First up is on. Here is the code for that:

on (eventName, callbackFn) {
  if (!this.events[eventName])  {
    this.events[eventName] = []
  }
  this.events[eventName].push(callbackFn)
}

Because functions are first class objects in javascript, which basically means they can be stored in a variable, an object, or an array, we can just push the callback function to an array stored at the key eventName in our events object.

Emit

Now, for our emit function.

  emit (eventName, eventData) {
    if (!this.events[eventName]) return
    this.events[eventName].forEach(fn => fn(eventData))  
  }

This solution takes advantage of what is called closure in javascript. If you are coding in Javascript in your interview, understanding closure can be vital. A closure is essentially when a function has references to its surrounding state or its lexical environment. You can also think of this as a closure allowing you access to an outer function’s scope from inside an inner function. Using global variables is a great simple example of closure.

Here’s another great example of using closure to track how many times a function was called.

function tracker (fn) {
  let numTimesCalled = 0
  return function () {
    numTimesCalled++
    console.log('I was called', numTimesCalled)
    return fn()
  }
}

function hello () {
  console.log('hello')
}

const trackedHello = tracker(hello)

The inner function returned in tracker closes over the variable numTimesCalled and maintains a reference to it for the life of the trackedHello function. Cool stuff huh??

RemoveListener

The removeListener method is probably the easiest of the three. Here is a solution -

removeListener (eventName, callbackFn) {
  const idx = this.events[eventName].indexOf(callbackFn)
  if (idx === -1) return
  this.events[eventName].splice(idx, 1)
}

And that’s the class! Pun intended :) Seeing if you can implement methods that are part of the language is a great way to practice for interviews. See you all next week!

How to build a side project that will impress future employers

elisabethgross — Tue, 21 Jan 2020 04:01:11 +0000

Hey everyone! Welcome to a special edition of Code Review, our weekly series of coding challenges and job related content. In this post, I’ll be talking about one of my favorite side projects, Breadwinnerss, and how you can impress future employers by flexing your coding and problem-solving skills! I’ll go over what makes for a great side project and how to talk about your projects on your resume and in interviews.

Remember, if you like this content and want more of it, subscribe to our newsletter here to receive the latest and greatest we are putting out on Dev.to and on Coderbyte.

Finding awesome project ideas

From a technical perspective, a good project idea is perhaps the least important part of any good side project. But, trust me, a compelling project that solves a real problem is way more impressive to an interviewer than another 'alarm clock app.' So how do you find awesome project ideas?

You might have your own, but since you're a developer, the odds are you know someone is good at identifying cool problems to solve. Personally, I connected with the founder of the first company I worked at Nis Frome. Entrepreneurs have a track record for problem solving and I've found that they usually have a backlog of ideas, big and small. You probably know more than a few who would love to partner.

Nis had a number of projects he wanted to work on, but one in particular required some cutting-edge tech, which made it attractive to me. Today, the project is called Breadwinnerss and it solves a problem that Nis is very passionate about: helping people in his network find jobs at companies in his network.

Every week Nis gets 5-6 requests from job seekers asking for introductions to companies he has contacts at. Before Breadwinnerss, Nis would spend time browsing career pages from companies in his network to make matches and intros. Breadwinnerss was born to help alleviate some of that manual work. We essentially built a massive web scraper that scrapes career pages and aggregates the jobs into one live feed (kind of like an rss feed… get it? Breadwinnerss?). That way, when someone asks Nis for an intro, he can just send them a single link to his Breadwinnerss feed where the user can request intros for whichever roles they're interested in across dozens of companies. Already, Nis and our other users have helped several people get really cool new jobs.

Flexing your dev skills

The main goal for this side project was to learn, so I specifically picked technologies that I hadn’t done much work with before. This is an excellent talking point in an interview. It’s an opportunity to show your interviewer exactly what you can do when faced with new or unfamiliar technologies which is essentially what will happen at almost every new job you ever take.

That being said, you don’t have to reinvent the wheel. For Breadwinnerss, I chose full stack Javascript because that is something I am comfortable with, but I chose almost all new frameworks and tools to go with it. I used Node and scraping libraries called Cheerio and Puppeteer to build the scraper. I deployed that to a Google Cloud function which runs daily. The scraper script itself scrapes each company’s career page with a custom scraper function I built and saves all those results to a file in an AWS S3 bucket. The web application part of Breadwinnerss is also built using Node, with express as the routing framework and Postgres as the database. The front end was built using Vue.js. The web app reads the scraped jobs from s3 and serves them to the front end. It lives on Heroku.

  filterDepts (data, $) {
    // needed to capture the class instance (at this point the 'this' context) which becomes the document in the cheerio callbacks 'this' context
    const that = this
    const filteredDepts = data.filter(function () {
      const dept = $(this).closest('.ptor-jobs-list__department-section').find('h2').text()
      return utils.myFilter(that.targetDepts, that.badDepts, dept)
    })
    const ret = []
    filteredDepts.each(function () {
      const jobTitle = $(this).find('a').text()
      const url = $(this).find('a').attr('href')
      const location = $(this).find('.ptor-jobs-list__item-location').text()
      ret.push({
        jobTitle,
        location,
        url
      })
    })
    return ret
  }
  filterJobs (jobs) {
    return _.filter(jobs, (job) => _.includes(usCities, job.location))
  }

Emphasize technical challenges and solutions

To a large extent, tech interviews are basically one big simulated problem-solving exercise. Can you troubleshoot? Can you learn quickly? Can you jump into a fluid environment and adapt? It's important to emphasize how you solved technical problems while building your project – it'll alleviate a lot of pressure during the interview.

One of the biggest changes we made to the architecture of the app was changing how and when the actual scraping happened. When we started, the initial proof of concept was just for Nis and scraping the 8-10 companies from his network. Naturally, I just scraped every company on page load of Nis’ Breadwinnerss feed. The scraper was coupled with the web application code and would get the latest list of jobs every time someone visited the feed. This actually worked for us for quite a while and doing that as our MVP allowed us to release an early working version. Some people might think that learning 5 things at once and perfecting the tech stack before release will look very impressive, but more often than not, it just prevents you from ever releasing it.

That was fine until we got to scraping about 20 companies. At that point, the request for scraped jobs was taking longer than the maximum Heroku will allow a request to last (about 30 seconds). This was when we decided to cache the results of each scrape in a file in an S3 bucket. We also moved the scraper code to be in a self contained module that we deployed to Google cloud functions to be run on a daily cron. All this allowed for feeds that load quickly and the ~100 companies we now include in our scrape every evening.

async function processCompanies (browser, companies) {

  const processedCompanies = []
  for (const connectorCompany of companies) {
    const { target_jobs, bad_jobs, target_depts, bad_depts, module_name, scrape_url, base_url, companies_name, company_url, type } = connectorCompany
    console.log(`Scraping ${module_name}...`)
    const companyModule = require(`./companies/${module_name}.js`)
    const connectorCompanyModule = new companyModule(target_jobs, bad_jobs, target_depts, bad_depts, scrape_url, base_url, companies_name, company_url, type)
    const result = await scrape(connectorCompanyModule, browser)
    processedCompanies.push(result)
  }
  return processedCompanies
}

Showcase projects on your resume

Most developers already put their GitHub profiles on their resume. If your project is in a public repo, savvy recruiters may check it out. But that's basically burying something that gives you a significant edge.

I'd recommend instead creating a dedicated section to call out your project, any cutting-edge tech used to build it, and any market traction or validation you have such as number of users or even revenue.

Main takeaways

In summary, here are 4 of my main tips when it comes to building a side project:

Find and solve a compelling problem.
Use the project as an opportunity to mess around with new technologies.
Iterate! Build a quick prototype in less than a month and then improve it based on user feedback.
Collaborate with friends who you wouldn't normally get to work with. Side projects don't have to be lonely!

Check out the code on github!

We felt it was important to make the code public so other people can learn from how we built this project. Go check it out on github and let us know what you think.