Algorithmic Problem Solving for Programmers

Algorithmic problem solving skills is one of the most important skills for a programmer. Great programmers are able to conceptually come up with solutions by visualizing and breaking down the problem into smaller parts. Afterwards, it is up to the programmer to write a clean, effective solution.

With the hope that this article will help you in your journey to become better at problem solving, I am going to write down my though process as I write up a quick solution to the merge sort algorithm. Depending on how much refactoring I plan on doing, I may write multiple parts to this post.

Anyhow, the purpose of this post is to journal my thought process when writing up the merge sort algorithm. Bear in mind that I have not written an implementation for merge sort in quite some time. In other words, I needed to start from scratch.

If you would like to skip straight to where I actually start coding, I recommend clicking on Implementation in the table of contents.

Understand the Problem

How can you solve a problem that you don’t fully understand?

Ever faced those moments where you make random changes to fix a bug and you feel like you are going nowhere? It is highly likely that this is occurring because you don’t fully understand what is causing the side effect/bug. This can be a result of a myriad of reasons.

For example, your knowledge of the tools that you are working with may be incomplete. Your code might be structured in a way that makes it difficult to debug. I have written a blog post on identifying bad code.

The same goes algorithmic problem solving. In this section, I am going to present to you my generic approach to solving problems. Please note that all cases are unique and there are times where you may need to try different approaches.

However, this will give you a springboard to dive into and discover ways of algorithmic problem solving that works best for you, as an individual.

Gather Information

The first step towards understanding the nature of a problem is to gather as much information as possible. As cliche as this may sound, the information gathering process, I would argue, is the most important stage.

People gather and learn differently. Some people like reading. Some people like watching videos. Others like diagrams and examples.

In the modern day and age, information of varying type (and quality) is all around us. Mastering the art of gathering good information and absorbing the information in a timely manner is the lifeblood of programmers.

How well you understand the problem domain will determine how accurately you can document the code, as well as optimize. When I say document, I am referring to writing a solution that is easy to maintain, read and understand. What I tend to do is the ask the following questions.

What is the purpose of my algorithm?

Essentially, you are asking – What are the use cases for the algorithm? The use case dictates the range of possible inputs. In most cases, when designing an API for an algorithm, users will likely be developers. Identify your target end users.

If a junior developer is going to be using your API, you want a very simple, easy-to use design that handles all the complex operations underneath the hood and returns the result. If an intermediate/advanced developer will be the consumer, you might want to make your algorithm more flexible to provide some customization options to broaden its range of usefulness.

Target end user categorization is a complex topic in it of itself, so I will leave it at this. In the near future, I may write a post addressing this issue.

What are the main obstacles and challenges?

algorithmic problem solving example

A problem is a problem because there are obstacles and challenges involved. Didn’t mean to sound sarcastic, but I wanted to emphasize the aforementioned statement to re-address the main purpose behind algorithms.

A problem is difficult to solve, because you have never seen a problem before or you (as of now) don’t know how to approach it.

Challenging problems (or most problems) are a union of smaller problems.

Our current case study: the merge sort algorithm perfectly embodies the aforementioned statement.

List what you know and what you don’t know

Start with what you know. In the image at the start, the student knows how to add and multiply, but doesn’t know what to do when they are combined. This student did the right thing by asking a question “Do I solve from left to right?”

Now the student needs to research and see whether that approach would be feasible through applied research and testing.

The operating environment and constraints.

Okay, the last point is not a question. However, it is important to know the constraints that you are given. For example, how much memory are you working with? What is the desired time complexity of the algorithm?

If you don’t understand what I just said, I recommend reading up on the Big O notation. I have also written an article about Big O as well.

In my current project, I had to optimize my algorithms to take up as little memory as possible. Therefore, instead of speed, the amount of memory used up by my algorithms was more important. Identifying and knowing these constraints will help you visualize the challenges that may appear, better equipping you to solve the problem.

Most of the times, these constraints will not be expressed technically, like “it has to run in O log (n)”. Good programmers are able to analyze non-technical descriptions and behavioral issues and translate it into technical specification and requirements.

Information on the Merge Sort Algorithm

Now, we will go back to the merge sort algorithm. We know that the purpose of our algorithm is to sort a list (in ascending order in my case).

What are any other requirements for my algorithm?

Because I know that the merge sort, by definition has a time complexity of o (n log n), I add that onto the list of requirements.

Draw Diagrams

merge sort algorithm tutorial conquer the sub-problems and join the result to derive the final solution

Because my memory is not that great, in order for me to properly visualize and understand what I needed to write, I drew out a diagram.

When it is confusing, I usually either write out each step as I draw it, or speak it out. For example,

“Okay Jay. The merge sort algorithm works by dividing an existing list into halves until we can no longer divide the list. A list of length one is technically a sorted list. Afterwards, we merge each of the single pieces to form a list. While merging the lists, we put the items in the list from smallest to largest. We continue this process, until we have one single list”.

Write Pseudo Code

Writing pseudo code is a great way to focus on the logic as opposed to getting caught up with writing actual code tied down by technical constraints. It allows us to write down our logic without having to worry about details outside of the logical aspect of solving a problem such as language details.

This allows us to have a holistic overview of the flow of logic in our program. Of course, we will naturally encounter bugs as we write out the actual implementation details in our language of choice. Writing pseudo code however, gives us another pair of lenses to examine the problem with. Naturally, this broadens our perspective and as a result, bugs are discovered much more quickly.

Pseudo code is a great way to document the key steps in solving a problem, which we will discuss in the following steps. Note that there are many different flavors/styles of pseudo code. Make sure that you are selecting the style that makes most sense for your target audience. For example, if you are writing pseudo code for Java developers, write it in Java style. If on the other hand, you are writing only for yourself, write it in a manner that makes most sense to you. Heck, you can even bend some conventions.

Here is a sample pseudo code snippet taken from wikipedia.

Sub fizzbuzz()
For i = 1 to 100
print_number = True
If i is divisible by 3 Then
Print "Fizz"
print_number = False
End If
If i is divisible by 5 Then
Print "Buzz"
print_number = False
End If
If print_number = True Then print i
Print a newline
Next i
End Sub

Analyzing Key Procedures when Solving Problems

Get your thoughts out of your brain and into the real world

When it is cooking Kimchi fried rice, it will look something like this.

  1. Crack open and egg and fry it.
  2. Add the ham, Kimchi and cook it steadily for 2 minutes.
  3. Continuously stir the rice for 5 minutes so that it doesn’t burn.

Anyway, just as it is with cooking, there are steps when solving a problem. Let’s take a look at the merge sort algorithm. Thankfully, even before asking questions, since I knew how the algorithm works by heart, I was able to come up with the following steps.

  1. In each iteration, divide the list in half.
  2. Repeat this process until the list length is one. Why? Because a list of length 1 is a ‘sorted list’.
  3. Join the pieces together by pair on each iteration. E.g. since 6 is less than 10, when joining into a list of length two, the first element will be 6, followed by 10.
  4. Continue joining/merging the lists until we have a single list. This will be our sorted result.

Being able to come up with these steps is a sign that you understand the problem domain. If you cannot communicate the steps in written form or verbally, it is a tell-tale sign that you do not understand the problem domain.

Write Code

If all the other steps were prototyping and preparing, writing code is the final step. Don’t be down if you don’t get the solution in one go (I tell myself this all the time haha). One of the purposes of this step is to test whether your logic is sound. Bugs/errors will be easier to debug provided that you understand the problem domain. The other part that will aid you is your experience as a programmer and your understanding of the language.

Therefore, it is extremely important that you code frequently, even if you are a professional full-time programmer. Code outside of work. Always work on side projects. Your hard work will not betray you.

Refactor

In case you have not noticed, the code above is sub-optimal in terms of memory usage. An in-place sorting algorithm would have been much more efficient and even if you wanted a brand new copy, there are much better ways to write the algorithm to remove redundant code and boost performance.

Refactoring improves your problem solving skills and ensures that your skills are growing so that the challenges of tomorrow can be solved not only quickly, but engineered to be consumed less painfully and run like a well-oiled machine.

Look for Extra Edge Cases

Ideally, you would have covered all the edge cases in your first write up, but more often than not, when the code is shipped, you start coming across some errors not seen during the testing phase.

The aforementioned case is a nightmare for developers. Keeping eyes peeled for edge cases is difficult. You naturally become better through

  1. Practice
  2. Experience

The more work you do, the easier it becomes to identify what could and has gone wrong in the pasts. Your experience and hard work will not betray you.

Ask Somebody

After I have a working implementation, I pass this code to somebody else and ask them to use it. If another developer uses it and comes across some weird edge cases, you have some work to do.

Thank them and buy them a coffee for saving you hours and possibly days of headache.

Implementation

If you read through all the sections before reaching here, just wanted to remind you that the algorithm we will be working with is the merge sort algorithm.

I literally wrote the entire implementation (including comments and debugging) in approximately 20 minutes. Yes, I screwed up my logic twice, once resulting in an infinite loop. What I did not count in the 20 minutes is the process of drawing out how the algorithm works on power point. The reason I did this, as I mentioned in previous section is to refresh my memory and also to double check that I understood what I was coding.

Before proceeding, I would like to remind readers that this is not the most optimal implementation of the merge sort in terms of both speed and memory. If I write more posts on algorithmic problem solving, I plan on writing one on refactoring, where I refactor this piece of code.

You may notice some parts that are sub-optimal or inconsistent variable naming and whatnot. I am going to try and add as much commentary as possible. However, if you spot something that you would like to bring up, please leave a comment. That would be very much appreciated :).

JavaScript Code

Here is the merge sort algorithm. I placed the merging process inside of a different function called merge, which accepts two lists – the left and right list.

/**
* Merge Sort Blind
*
* FYI, this took me 20 minutes to write up, which includes
* fixing bugs, writing comments and whatnot.
*
* Before starting, for me, I need to visualize the algorithm
* This results in me doing poorly in timed coding interviews
* Because I tend to skip the visualization phase and move onto coding,
* which results in me missing out on key logic or failing to consider some
* edge cases.
*
* Anyway, I am going to write out my entire thought process in the comments
* so it may get a little cluttered.
* */
function mergeSort(inputs) {
// Thought 1: base case
// Because an array of one length is technically sorted
if (inputs.length < 2) {
return inputs;
}
// Need to math.ceil to round it up, since
// in JavaScript, numbers are floats.
// We are rounding it up because the length property is one-based
// whereas indexes are zero based.
var middle = Math.ceil(inputs.length / 2);
// Split the array into halves.
// We are going to do it the old fashioned way using loops
// so that we all see how this works
var index = 0;
// Declare left and right array.
var leftArr = [], rightArr = [];
// left Array insertion
for (; index < middle; index++) {
leftArr.push(inputs[index]);
}
// Right array insertion.
for (;index < inputs.length; index++) {
rightArr.push(inputs[index]);
}
// call mergeSort recursively.
leftArr = mergeSort(leftArr);
rightArr = mergeSort(rightArr);
// Now that we have our array, we are going to
// recursively work on splitting the array until we
// have an array of length one, which is technically
// Sorted.
// Afterwards, we need to stitch the results back
// In a sorted manner.
return merge(leftArr, rightArr);
}

And here is the merge function. Because this is for educational purposes, I have written comments describing my thought process behind each line.

function merge(leftInputs, rightInputs) {
var sortedResults = [];
// We are going to continue sorting until one of the arrays is empty
// Technically if one side is empty, that means that the result is sorted.
// Afterwards, we dump the results from the non-empty array into the sorted results
while (true) {
// Left is empty, so dump all the sorted results into the array
if (!leftInputs.length) {
while (rightInputs.length) {
sortedResults.push(rightInputs.shift());
}
break;
}
// Right input is empty, so dump all results into the sorted result
if (!rightInputs.length) {
while (leftInputs.length) {
sortedResults.push(leftInputs.shift());
}
break;
}
// Both left and right list are not empty, so start comparing.
// Remember, we only operate on the first element on each array
var left = leftInputs[0];
var right = rightInputs[0];
// Compare and remove the first element from the array
// It is important that we use shift to remove the first element and
// place it in the sorted result
// Otherwise, we get an infinite loop
if (left <= right) {
sortedResults.push(leftInputs.shift());
} else {
sortedResults.push(rightInputs.shift());
}
}
return sortedResults;
}
var arr = [1,7,28,81,8,2,4,7];
console.log(mergeSort(arr));

The JavaScript code can also be found on GitHub.

Debugging Code

This might seem embarrassing, but out of the 20 minutes of coding, I spent a good 8 minutes debugging my code.

In most cases, you won’t reach the solution in one try, especially if you are solving a relatively challenging problem. Debugging skills are not only honed through practice, but also adopting a mind that embraces analytical and critical thinking.

My personal rule of thumb is – debug for 30 minutes and figure out what the problem is.

If I cannot figure out what is causing the bug in 30 minutes, I take a break. Take a coffee break with co-workers. Go out for a walk. Work on another task.

Whatever it is, stop what you are doing. In my case, when I work on debugging and I can’t find out what is causing the bug in under 30 minutes, I am under the developer’s tunnel vision. From experience, everything goes downhill if I continue to persist.

Oddly enough, whether it is for work, or a personal project, you will be surprised at how easily the answer comes after a good night’s rest, shower or from a break where your mind is no longer preoccupied with that problem. I have literally had moments where I wake up at around 6am in the morning with the realization of what was causing that issue. When I got to work and implemented the solution, lo and behold, IT WAS WORKING!

If you are repeatedly spending hours and hours debugging without any results, would be a great idea to evaluate the effectiveness of your debugging strategy. Because each individual processes differently, my approach will most likely not work for you. Try experimenting, and find out what works best for you!

Evaluate Existing Assumptions

The first thing that came to my mind when coding was the base case. When it comes to repeated tasks, my brain generally floats towards a recursive approach, because it is easier to read and understand (well, for me). Note however, that each recursive call adds that function to the call stack. Ideally, an in-place algorithm would be more performant, especially in terms of memory, but I was not going for the most optimal approach the first round.

If you are faced with a challenge, try solving the problem first. Use brute force, do whatever is necessary.

Once you have a working solution, it becomes easier to identify patterns/ways to optimize your solution.

Make sure that you are solving the problem first in the most optimal way that comes first to mind. Trying to come up with a super fancy problem on the first go will leave you open to more bugs, which generally equates to more time wasted.

Lessons Learned

Solving a problem is close to meaningless if nothing is learned through the process.

This is why many developers discourage the practice of copying and pasting (myself included). I even wrote an article on some ways to become better at problem solving, which you can read here.

It’s great that you solved a problem and your client is happy. I would like to mention that, if you did not learn anything from solving a problem, all you did is exchange your time for money. In the case of a job, that is fine, but if you are working on a side project with the focus on learning and growing, then this is a problem.

Make notes (yes actual written notes) on what you learned to deepen your existing pool of understanding.

Here are some questions that you can ask to guide you through this process if you are uncertain on where to start.

  1. What was the greatest challenge / difficulty faced when solving the problem.
  2. If you could re-solve this problem, how would you have approached it.
  3. What were some ‘mistakes‘ that you made? List some of the reasons why you took those courses of actions and some possible ways to avoid making similar mistakes in the future.

Anyway, I hope that this article cleared some layers of ambiguity in your approach towards algorithmic problem solving.

Thanks for reading!

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community. I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.

follow me on:
9 Shares