Let’s Solve HackerRank Challenges (with Golang)

Hi Everyone,

Sometimes, we fall into a loop where we work same problems and use the same algorithms which may block us to learn new things. so with this thought today I wanted to break the loop for you :), and try to explore new methods to solve Hackerrank questions in different ways and tell all details

Let’s start First Problem,

What is Problem

Our first problem is “Sales by Match”, That’s a matching problem about socks :). You can imagine a big stack of socks that have different colors and of course, they are messy :)

So, Problem wants what we can match same colored socks and wants to know how many pairs of socks will be able to be available for sale

We have 4 pairs of socks in 9 socks

Solving Ways

1. We can hold all socks single by single and find pairs of that on other socks.
2. We can sum counts that same color socks to a small paper by looping all of the arrays, and we can div all colors’ counts by half to find a result
3. We can keep sock status as pair or single by looping all of the arrays, and when a color has been paired, we can increment the total pair count to find a result

Let’s start to review all ways

1. … hold all socks single by single ...

We find all pairs of socks like that;

For each sock, We need to check the remainder socks, so It means our complexity is (N-1)+(N-2)+…+1, so It’s equal to ((N-1)*N)/2, so we can say our complexity O(N²).

You may have said It might be done with fewer efforts when some cases, It’s correct but We should not forget what complexity is calculated with maximum effort size.

Sample Code:

func FirstMethod(arr []int) int {
   total := 0
   for i := 0; i < len(arr)-1; i++ {
      for j := i + 1; j < len(arr); j++ {
         if  arr[i] != -1 && arr[i] == arr[j] {
            total++
            arr[j] = -1
            break
         }
      }
   }
   return total
}

2. … sum counts that same color …

This way has less complexity than before because we don’t need to check all socks’ pairs, only It will be enough to keep counts of all colors.

Each step works only 1 time and It means this way has 1 x N complexity to keep colors counts, but do not forget to div all counts of colors to half, because we need to pair counts for all.

So how much does this splitting process cost? We’re defining this process as V. V can be less or equal to N. When all socks have different colors, the color count may be equal to the socks count

If all socks have different colors, the complexity of this will be equal to 2N, so It’s O(N), also If all socks haven’t different colors, It’s equal to N+V, so V is less than N and we can say O(N) as complexity.

Sample Code:

func SecondMethod(arr []int) int {
   results := map[int]int{}
   for _, n:= range arr {
      if _, ok := results[n]; !ok {
         results[n] = 1
         continue
      }
      results[n]++
   }
   total := 0
   for _, v := range results {
      total += v / 2
   }
   return total
}

3. … keep sock status as pair or single …

sometimes reading is very tiring to us if the article has many different solutions, I know, but this is the last way to the solution, also don’t forget to check the Benchmark results under the solutions section.

at now, we will only keep results that color is pair or single, so If the color will be pair, we will increment the total count.

It’s working only N times for all of the steps, so It’s equal to O(N), also why we should keep all colors count, If we won’t use it?

Maybe, You are wondering why we care that not keeping counts. Its reason on the next section as Benchmarks

Sample Code:

func ThirdMethod(arr []int) int {
   total := 0
   results := map[int]bool{}
   for _, val := range arr {
      if status, ok := results[val]; ok && status {
         results[val] = false
         total++
         continue
      }
      results[val] = true
   }
   return total
}

Benchmarks

If we try to test with 20 items for each array, we can see the following results.

BenchmarkFirstMethod    73.21 ns/op    0 B/op    0 allocs/op
BenchmarkSecondMethod  638.4 ns/op   357 B/op    3 allocs/op
BenchmarkThirdMethod   483.7 ns/op   196 B/op    1 allocs/op

So with these results, we can ask “why did we try to use the second and last method, and complexity said a lie to us, otherwise, how can N^2 be fast than N, we saw less cost here”. We had a confusing, but you should not panic, I will explain all

If we try to test with 500 thousand socks and about 200 thousand colors, we can see these results

FirstMethod  19626222459 ns/op         0 B/op          0 allocs/op
SecondMethod    19779549 ns/op  11303742 B/op       6653 allocs/op
ThirdMethod     18002153 ns/op   7073057 B/op       6584 allocs/op

That was very interesting when after we saw the first result because all things changed and our last method has been the best method. Why? Because our first method can solve easy problems in a short time as easily, but If we try to solve hard problems with it, It can not works well.

For 500.000 socks and ~200.000 colors
First Method Result: 19 seconds with 0 byte memory
Second Method Result: 0.019 seconds with 11 MB memory
Third Method Result: 0.018 seconds with 7 MB memory

Summary:

• When socks and color count are less, We can use the First method,
• If we have a complex problem, We must use the Second or last method.
• If we have a memory limit, We must use the First method, because others use memory to keep socks count or socks status.
• If we don’t know our inputs, we should use the Last method. I tried to show you all results from 5 items to 1 million items arrays

We can see the details on the following chart, I love charts because they would show all details to us

That’s all of today, so I want to say thanks for reading. If I would give some idea of complexity and problem-solving methods, I will be happy. See you next Hackerrank problem.

If you want to try different ways to solve this problem, You can access the following link to the question

Sales by Match | HackerRank

Alameddin Çelik