Ady Ngom

Truth be told I’m not a fan at all of algorithm code challenges. That might be surprising to hear from someone who’s putting up a tutorial on how to solve one, and who on top of it has made a mission of ‘fixing the Javascript Interview process. You might want to read more about that on the article below.

28 Relevant Javascript Interview Questions – Part 1

The reality is that, if you are to get hired anywhere as a Javascript developer, it would be hard and almost impossible in the current state to bypass these types of challenges.

Hacker Rank is the perfect playground to get your feet wet and build up your algorithms-building skills. The Sock Merchant challenge is one of the fun ones. It might be a bit scary if you have never been presented to problems this way, but I can guarantee you that you are subconsciously solving way more complex ones every day.

The challenge

Hacker Rank Sock Merchant Page

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

Two Solutions in less than 5mn of video

But if you are more the reading type, a quick explanation and the transcripts are just below to feed your cravings.

Solution 1 — Sort, compare and count pairs

In the first two minutes of the video, I explain the approach of sorting the passed in array first, and looking at each item side by side to find and increment the pair count. The final code produced is below.

function sortAndCount( n, arr ) {
    let sorted = arr.sort( (a,b) => a - b);
    let pairs = 0;

    for (let i = 0; i < n -1 ; i++) {
        if ( sorted[i] === sorted[i + 1]) {
            pairs++;
            i += 1;
        }
    }

    return pairs;
}

function sockMerchant(n, ar) {
    const colors = {}
    let pairs = 0;
    for (const color of ar)
        if (colors[color]) {
            colors[color] = 0;
            pairs += 1;
        } else {
            colors[color] = 1;
        }

    return pairs;
}

const n = 9;
const socks = [10, 20, 20, 10, 10, 30, 50, 10, 20];

console.group('Sorted and counted');
    console.log(`There is a total of ${sockMerchant(n, socks)} pairs`);
console.groupEnd();

And here is a complete transcript of the first segment

Video transcript — segment 1

So one way to solve for the sock merchant challenge is to sort the array, compare each item side by side to find a pair and total the number of pairs we find

So our first step, we will create a variable to hold the sorted array and use the built-in sort method the sort method can take a compare function as an argument. The passed-in compare function will ensure that items are sorted in ascending order

Next, we create a pairs variable which will hold the final count, we default it to 0

At this point, this would be the expected output from sorted if we were to pass in our socks array

Next, we set up a for loop. 
We naturally start at index 0 but since we are going to compare items side by side we make a full stop at last index

Now we can compare each item of the array with its direct sibling to
Find a pair

We increment the pair’s value if we find a match. We also increment i 
By one to skip the next item since we have already checked it

If the two items do not match the normal loop cycle will continue

We have now sorted and compared side by side let’s run our solution

Solution 2 — Dictionary, stock and count

The second and better performant approach is to create an object on the fly that stores the numbers of times each sock appears using the sock id as key.

When ran on a set of 10,000 items, it outperforms the first solution by a 400% gain in speed. Below is the produced code

function stockAndCount( n, arr ) {
    let pairs = 0;
    const colors = arr.reduce((acc, val) => {
        (!!acc[val]) ? acc[val] += 1 : acc[val] = 1;
        return acc;
    }, {});
  
    Object.keys(colors).forEach( n => {
        let _pair = parseInt( colors[n] / 2);
        if ( _pair >= 1 ) pairs += _pair;
    });

    return pairs;
}

const n = 9;
const socks = [10, 20, 20, 10, 10, 30, 50, 10, 20];

console.group('Stocked and counted');
    console.log(`There is a total of ${stockAndCount(n, socks)} pairs`);
console.groupEnd();

And again the video transcript for the second solution at 2mn:15

Video transcript — segment 2

In part 1 we solved the challenge using a sort first and compare approach, let’s clean up and look at an alternative solution.

Using the stockAndCount function, we will create an object that will stock each of our colors as keys.

So we will still create a pairs variable, then we will have a colors variable here but using the reduce method here we will be building up this object as we go.

In the reduce callback we setup an accumulator and the current value — doing this on the fly we check to see if our current value exists as a key in our accumulator object, if so we add one to it if not we create the key and initialize it with 1.

Let’s not forget to add the empty object as the second argument and return the accumulator after each iteration

Let’s make sure the function is properly closed

What we have done above is what I call the Dictionary approach.

Now that we have an object with each color as a key ket’s loop through it.

We iterate through each key and we create a local pair variable. We initialize the pair by dividing the colors n key value by 2

Now we can check if the pair value is greater or at least equal to 1. If true we can increment the total pairs value on line 17 with the number of pairs found

We can then simply return the total count after the loop. Running it in the terminal gives us again 3 pairs — If that went too fast let’s add to our console statement and run it again

Conclusion

I will leave out intentionally the whys the second one is way more performant than the first one and I can assure you that one of you smart folks will come up with yet others that will leave the second in the dust. Please add to the discussion and share in the comments

What is most important and that they have both in common is that though they might seem naive at first, they do work and provide the right answer. Solutions can and will always be improved and refactored, but wrong will never magically turn into right — at least in this tech realm that we live.


I have always been a big advocate of explaining complex concepts in simple terms. This was at the core of the different Front-end related meetups I use to run in San Francisco California. I'm first and foremost a learner at heart. I really shy away from the word expert, but Javascript and the ecosystem of libraries and frameworks around it have been my passion and work for the last 15 years. I hope that you will carve a space in your busy digital lives and join me in this great learning journey.

View Comments

There are currently no comments.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Next Post

like the content?

I write about 4 articles  a month and link to a few useful resources. Get a cool weekly newsletter.

Subscribe now