HackerRank: Sales By Match
If you’re like me, practicing a code challenge is probably the one thing that’s got you feeling extremely nervous about that technical interview coming up soon, or even tomorrow! That’s okay, they are meant to be challenging, otherwise, they wouldn't be called code challenges!
Luckily, they are not impossible to solve, unless someone out there has created the world's most complicated algorithm — which would just be incredibly unnecessary.
Aside from all of the “what ifs”, I am here to talk about an algorithm I struggled solving!
Sales By Match
There is a large pile of socks that must be paired by color. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.
n = 7
r = [1, 2, 1, 2, 1, 3, 2]
There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.
Complete the sockMerchant function in the editor below.
sockMerchant has the following parameter(s):
int n: the number of socks in the pile
int ar[n]: the colors of each sock
int: the number of pairs
The first line contains an integer n, the number of socks represented in ar.
The second line contains n space-separated integers, ar[i], the colors of the socks in the pile.
— — — — — — —
10 20 20 10 10 30 50 10 20
n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]
From what I have gathered, we have out integer (n) that tells us how many “socks” are in our array. We have an array, in that array we have a few repeating elements that represent a sock. We also have an output of just an integer of how many pairs of socks we should be returning. So far, so good!
How should we approach this problem?
What I like to do is ask myself, “What can we do with what we know?”, this usually leads to verbal pseudocode
//check to see if array === valid
//we need a counter for how many pairs we encounter
//i can create an object to store a key/value pair// can now iterate over the array
--> //for every sock in array, if that sock has already been encountered we add 1 to it's value || if not we start off with 1
1st encounter 20: 1
2nd encounter 20:2 //iterate over the array again to count the pairs
--> // for every sock in array, if that sock's value is divisible by 2 increment our counter !
20: 2 <-- 2 % 2 === 0 //=> yes!
counter += 1
//return our total pairs
The time complexity of just one for of loop is O(n) which is called “Linear Time”. However, since I used two for of loops that is what is called “Quadratic Time” because I am going through each element in the array a second time! Therefore, my solution would have a time complexity of O(2n) and when we drop the constant, it would be O(n) , which is an ideal solution.
Considering the fact that I have an obj variable to store each element into a key/value pair. I believe this is called a “Hash Table”. Since my solution is looking up an object property is O(1), this will result in giving my solution a little boost in speed, making it now O(n)!
Thank you for reading! Keep Coding! Keep Learning, Keep Growing! :)
What helps me understand Big O Notation:
Big O Time Complexity: What it Is and Why it Matters For Your Code
How to understand the efficiency of your code, and communicate this efficiency effectively to other developers.
If you want to try your hand at optimizing my code better here is the link to “Sales By Match”: