This is the 4th part of my learn-in-public shinazz, with me taking a crash course on Algorithms and data structures. In this post, we will talk about a 5-step process I learned in solving programming problems. It's a 5-step process that should help you on implementing and solving complex requirements.

Steps in solving programming problems:

  1. Understand the Problem
  2. Concrete Examples
  3. Break it down
  4. Solve or simplify
  5. Look back and refactor

Understand the Problem

Software development is mostly figuring out how to deliver a set of requirements. So the first step is obviously to understand what the requirement is. It'd be a bummer if our implementation ended up as something that wasn't envisioned. To avoid wasting time, it'd be best to first understand what the problem is, and what is the expected output of the particular request.

The best way to do this is to repeat the requirement in our own words and ask the requester if we understood the details properly. For example, the problem is: "Create a function to determine if a triangle is equilateral, isosceles, or scalene". You may ask for clarification by repeating the requirement based on your understanding, if there are parts of the requirement that you did not understand, or you feel like that the requirement details needed expounding.

You may say something like:

So is it correct that the function would return a string, with the possible strings being "equilateral, isosceles, or scalene"?
Is it correct that the value that would be passed to the function would be an array of 3 numbers, since triangles have three sides?
Also, what if an invalid value was passed into the function, what should the return value be?

These types of questions would allow you to better understand what the expected result is.

Concrete Examples

The next step is to write down how the function would be used. For problems/requirements that is a little bit of a "big picture", we might want to create User Stories, but for a "simple" problem like what we stated above, we could be better off with simple code examples that we might call as Unit Tests.

Why is this important? Well, coming up with examples would help us understand the problem better, and also it would help us figure out the limitations and possible fallbacks.

For example, with the same problem we stated above, we might play around some sample codes that would strikingly resemble unit tests (if we added assertions instead of comments) as such:

getTriangleType([4, 4, 4]); // Should return "equilateral"
getTriangleType([4, 4, 8]); // Should return "isosceles"
getTriangleType([4, 5, 6]); // Should return "scalene"

// But what if we did not pass anything? Or values that isn't an array? Or an array that does not have 3 items?
getTriangleType();
getTriangleType(1);
getTriangleType("hello");
getTriangleType([0, 1]);
getTriangleType([0, 1, 2, 3]);

// How about triangle inequality?
getTriangleTypes([0, 0, 0]);
getTriangleTypes([1, 1, 4]);

By just doing this, we were able to see what conditions we might want to clarify first. We would be able to think about what is needed to handle the expected parameter, and depending on the requestor's clarification, we would be able to ready-up our function to handle unexpected values.

Break it down

With a better understanding on how the function would be used, and how it should behave, we can move on to writing some sort of pseudocode for complex problems, or just a draft while we break down what needs to be done to achieve the requirements.

Continuing with the example problem above, we know that a valid parameter is an array. We would need to iterate through that array and check each value to figure out how many are equal values, and return the appropriate string.

function getTriangleType(sides) {
  // loop through sides
    // check the count of the current side. If 3, return equilateral, if 2, return isosceles
  // If we passed the loop without a return value, then it must be that all sides are unique
}

This is the simplest pseudocode for the problem that comes out of the top of my head, without accounting the invalid values. Maybe add another comment right before the loop to consider invalid parameters like non-array parameters, or an array size that isn't 3.

Solve or simplify

With that out of the way, let's code. We will first simplify the code, with an objective of just "passing" the main requirement, with an added checks for invalid parameters that is easy to do. Based on the pseudocode above, we might come up with the ff. code:

function getTriangleType(sides) {
  if (
    !sides instanceof Array || 
    sides.length !== 3 || 
    sides.find(side => side === 0)
  ) {
    return 'invalid';
  }

  for (let side of sides) {
    const count = sides.filter(item => item === side).length;
	
    switch (count) {
      case 3:
        return 'equilateral';
      case 2:
        return 'isosceles';
      default:
    }
  }

  return 'scalene';
}

This should work with valid values and most of the invalid values, apart from triangle inequality. To also handle that, we could check some of the formulas that we can use to avoid many loops... Particularly this formula:

{\displaystyle 2\max(a,{\text{ }}b,{\text{ }}c)<a+b+c}

Since JS does not have a built-in helper function to find the largest value in a given array, we might need to go with reduce. We could use sort too, but JavaScript's built-in sort is O(n * log n), which is slower than reduce which is O(n). Now, we're not yet in the 5th step of problem solving, but since we already are aware of this, might as well go with reduce:

function isInequal(sides) {
  const max = sides.reduce((prev, side) => side > prev ? side : prev, 0);
  const sum = sides.reduce((sum, side) => side + sum, 0);

  return 2 * max < sum;
}
                      
function getTriangleType(sides) {
  if (
    !sides instanceof Array || 
    sides.length !== 3 || 
    sides.find(side => side === 0) ||
    isInequal(sides)
  ) {
    return 'invalid';
  }

  for (let side of sides) {
    const count = sides.filter(item => item === side).length;
	
    switch (count) {
      case 3:
        return 'equilateral';
      case 2:
        return 'isosceles';
      default:
    }
  }

  return 'scalene';
}

With that said and done, let's move to the 5th step

Look back and refactor

The fifth step doesn't mean that we should always refactor our code... it's more of to review what we've done. This is a good time to check the performance of our code using the Big O notation that we've learned so far (albeit we haven't yet really talked about O(n * log n) nor have we talked about O(log n) yet).

Our getTriangleType method is... O(n ^ 2) due to the filter inside our for loop. Since a triangle is always 3 sides, and having a larger array wouldn't end up on our for loop, it's still best if we can avoid iterations inside the loop... Maybe we can make use of an object instead? Doing this would also allow us to use reduce instead of a for loop. Let's get rid of the nested iterator:

function getTriangleType(sides) {
  if (
    !sides instanceof Array || 
    sides.length !== 3 || 
    sides.find(side => side === 0) ||
    isInequal(sides)
  ) {
    return 'invalid';
  }

  const hashmap = {};
  const count = sides.reduce((prev, side) => {
    hashmap[side] = hashmap[side]++ || 1;
    return hashmap[side] > prev ? hashmap[side] : prev;
  }, 0);

  switch (count) {
    case 3:
      return 'equilateral';
    case 2:
      return 'isosceles';
    default:
      return 'scalene';
  }
}

Now that's O(n) right there.

We might be able to further optimize the code above, but our objective here is to just demonstrate how these 5 steps could help when solving problems.

This could also help during interviews if ever the interviewer requires you to solve a particular problem in the white board. Interviewers tend to look for the candidates' thought process when solving problems, as this tends to hold more value than the person's familiarity of a particular tech stack or language.