Blogging My Programming Challenges

Lately I've been applying to dozens of developers jobs with no success. Either I would receive the infamous "we've decided not move forward with your application" email, or nothing at all. And while I know this process takes an amazing amount of patience, I'd be lying if I say I'm not pissed at my current situation. My resume is good enough dammit!

But as I think back on the denials, I start to wonder, would I have made it past first interview anyway? These startups and companies could be sparing me the embarrassment. I've been so focused building up my React portfolio, messing around with X and Y frameworks, that I've neglected to improve my problem solving and algorithm design skills.

Most of us know that white boarding isn't the best way to assess a developer/software engineer, and there are many companies don't bother with them. But the reality is, there are a lot of great companies still using this method. It is what is, for now.

Which is why I decided to do a code challenge per day and every so often document my process to share with the dev.to community. I could list all the reasons why this will be beneficial but Ali Spittel can do it better.

I don't question my ability to finally receive an interview but my chance of getting past that interview is what I'm not so sure of. It's also important because I have a master's in computer science and I feel I should be better at algorithms than I actually am. So even though I know how little a degree matters nowadays, I want to make it mean something to me.

With said lets get coding!

Between Two Sets

My first challenge was called Between Two Sets. Given two arrays, the objective is to create a function that returns an integer denoting the number of integers that are BOTH multiples of all numbers in the first array and factors of all numbers in the second array. These numbers will be between two sets

For example:

a1 = [2,4];
a2 = [16, 32, 96];
getNumbersBetween(array1, array2); // returns 3
// the three numbers, 4, 8, 16, are between the arrays a1 and a2, because they 
// are multiples of 2 and 4. And they are also factors of 16, 32 and 96.

The way I decided to approach solving these challenges is if I can't think up a working solution in 20 minutes I'll search for the solution, because in the real world I probably would have already failed the interview. Before I approached my time limit, I at least knew that I would need to find the lowest common multiple(LCM). I just didn't know how to find them in an algorithmic way.

I saw an answer in the HackerRank discussions which completed my thought process. The solution was to find the LCM(yes, I was close!) of the first array and the greatest common divisor(GCD) of the second array.

To find the greatest common divisor:

function gcd(a, b){
    while(b > 0){
        var temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

This function continuously finds the remainder of two numbers, a and b. While b is greater than 0, the current value of b will become the new value of a and the remainder will be the new value of b. Once the loop breaks, the function will return the GCD, which will be the last known divisor that was used to evaluate a remainder.

Here's an example of how this function works:

gcd(35, 14):

1st loop: 35 % 14 = 7
2nd loop: 14 % 7 = 0 //loop ends because the remainder is not greater than 0;

7 is the greatest common divisor

However, we have an array of numbers and you can't find the greatest common divisor of more than two numbers at a time. So you must create a function that takes in the array as input to iteratively find the GCD, two elements at a time:

const gcdOfArray = array => {
    result = array[0]
    for(var i = 1; i < array.length; i++){
        result = gcd(result, array[i])
    }
    return result;
}

Now that we know how to retrieve the greatest common divisor, finding the least common multiple is less of a pain. The LCM, with respect to a and b, is just the product of a and b divided by their GCD:

const lcm = (a, b) => {
    return (a * b) / gcd(a, b);
}

Again, we are not just dealing with two numbers so we need a function to find the LCM of an entire array:

const lcmOfArray = array => {
    result = array[0]
    for(var i = 1; i < array.length; i++){
        result = lcm(result, array[i])
    }
    return result;
}

Now that we are able to find both the LCM and GCD, to find all the numbers in between, we need to loop through the multiples of the LCM until the last multiple is equal to or greater than the GCD:

var lcm = lcmArray(a1); //lcm of first array
var gcd = gcdArray(a2); //gcd of second array

for(var i = 1; i*lcm <= gcd; i++){
    /*
        loop though multiples of our least common multiples
        until it reaches the greatest common divisor
    */
}

Using this loop, we can check if the current multiple is a factor of the GCD by performing a modulo expression. If this statement is true then count it as a number that is between two sets:

var lcm = lcmArray(a1); //lcm of first array
var gcd = gcdArray(a2); //gcd of second array
var count = 0;

for(var i = 1; lcm * i <= gcd; i++){
    if(gcd % (lcm * i) == 0){
        count++
    }
}
return count // the number of integers between two sets

Voilà!

And that's it, you can check the entire function at my gist here. Looking at the entire code in full was hard to grasp for me, at first. But once broken down, it actually got pretty simple. If you've seen any mistakes or know of a better algorithm, I'd love to know! Until the next challenge...✌️🏾