How to Solve Sock Merchant Code Challenge

Jojo Zhang — Thu, 02 Jul 2020 21:48:17 +0000

I started the Interview Preparation Kit on Hacker Rank yesterday. The thought of why not sharing how I solve those problems came to my mind. And here I am!

In this article, I'll use the UPER (Understand, Plan, Execute, Reflect) way of the problem-solving framework that I learned in Lambda School Computer Science Curriculum to walk through problems.

The challenge

HackerRank Sock Merchant Challenge 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.

Step 1: Understand

In this step, I'd dissect the problem into following questions,

What is the goal?
To count the number of how many pairs of socks. This also gives info that the final result should be an integer.
What do I have for parameters?
- n: the number(interger) of socks in the pile
- ar: an array of the colors (also integer to represent the value of each color) of each sock
How to achieve the goal?

In order to count pairs, we need to know what a pair means in this situation. Since the value of colors are different numbers, finding 2 of the same numbers will qualify a pair. Then we can add up those pairs.

Step 2: Plan

Implement the Input Example Implementing the input example in real life helps me figure out the algorithm. I keep asking myself how I would do it in real life. ```

n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]

To put in a visual way, I made this simple illustration via [draw.io](draw.io)
![Imgur](https://imgur.com/3kWA88v.png)

In order for me to find pairs, I would sort this array first. 
![Imgur](https://imgur.com/dzSqVZm.png)

Now, we can easily see and count that there're 3 pairs.
![Imgur](https://imgur.com/eJ8PU40.png)

With the help of an example and visual graph, I feel like I fully understand the problem and have a good plan in mind.  Now I can start to write some pseudo-code to help me translate the logic to code. 

### Step 3: Execute
- **Write Pseudo Code**
```javascript


//Need to initiate a count variable to count pairs and return the value
//sort the given array
//loop through the sorted array 
//if the current item equals to the next item 
//then that's a pair, increment our count variable
//also increment i to skip the next item
//return the count value

Time to Code ```javascript

function sockMerchant(n, ar) {
//Need to initiate a count variable to count pairs and return the value
let count = 0
//sort the given array
ar = ar.sort()
//loop through the sorted array
for (let i=0; i < n-1; i++) {
//if the current item equals to the next item
if(ar[i] === ar[i+1]){
//then that's a pair, increment our count variable
count++
//also increment i to skip the next item
i+=1
}
}
//return the count value
return count
}


### Step 4: Reflect 
There are 2 tricky parts of this solution
1. Do not loop through the last item since we compare the current to the next item. There's no next item to the last item. and will throw an error
2. When a pair is found, we also need to increment the looping index to skip the paired item

Other reflections including time complexity: there are definitely better solutions for time complexity since I sort the array first (O(n log(n))) and a for loop (O(n)). 


This is how I solved this problem with UPER.  Documenting the thought process is fun.  I'll keep writing.  Hope you like this.
Have a great day, everyone :)

DEV Community: Jojo Zhang

How to Solve Sock Merchant Code Challenge

The challenge

Step 1: Understand

Step 2: Plan