Problem solving tips and a breakdown of my problem solving approach
Tags: beginners, computerscience, productivity, problemsolving
Published: 2020-11-17 14:23:39

In this post I would like to break down my problem solving approach by solving an interview problem, and give you some tips that could hopefully help you in your own problem solving.
I will be solving a simple problem, but I'm hoping that the tips given here will be useful, not just interview questions, but also for more practical problems.

# Table of contents
* [Problem solving tips](#problem-solving-tips)
* [The problem](#the-problem)
* [Breaking down the problem](#breaking-down-the-problem)
* [Naive solution](#naive-solution)
* [Improving on the naive solution](#improving-on-the-naive-solution)

# Problem solving tips
A big impact on your problem solving abilities has your prior experience and knowledge. If both of those are higher you will have an easier time solving the problem.
But how do you handle a problem which seems impossible, one where you don't even know where to start?

![stuck on a problem](https://dev-to-uploads.s3.amazonaws.com/i/ujrgwp6099ss6lbdda8o.jpg)
* **Visualize the problem**. Try drawing a graph, a diagram, represent your data in a table or in a matrix. Visualizing the problem can give you a new perspective of the problem, which might be just what you need to get to a solution.

* In case you have a problem with a set of examples, like the one in this post, you could **try making more examples**. They could help you discover some missing link that wasn't as noticeable before.

* If you are stuck for a long time, it might be worth looking at the problem again, **making sure that you didn't misunderstand** something or assumed something that isn't true about the problem.

* **Take a break**, if that is an option. Looking at a problem with a fresh perspective can make a huge difference. When we are focusing on a problem, we can subconsciously focus on one particular way of solving the problem, which isn't necessary the best way. After you take your mind off the problem and come back to it later, you might get a new idea.

* **Ask somebody for help**. Sometimes our lack of knowledge or experience might make it impossible to get to a satisfactory solution on our own. Two heads are better than one.

* **Google is your friend**, there is no need to reinvent the wheel.
Unless you are solving a problem for an interview, or to practice your problem solving skills, you should try looking for a solution online.
If you can't find the solution for your exact problem, try looking for similar problems.

* Always **use intent revealing names** for your variables, functions, etc. It might seem like it doesn't matter sometimes, but it does, especially for complex code. Your brain shouldn't have to worry about figuring out what your abstract variable names mean, it should be focusing on the problem at hand.

* **Don't give up**. You will get there eventually as long as you don't give up.

# The problem
The problem that I will be going over is called the "two sum problem". It's a popular interview question ([source](https://www.coderbyte.com/algorithm/two-sum-problem)).

It goes as follows:
>**"Find all the pairs of two integers in an unsorted array that sum up to a given S."**

>For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because
>11 + (-4) = 7 and 2 + 5 = 7.

# Breaking down the problem
The first thing we should do is make sure that we **understand the problem and its constraints**. It's easier to do that after we break the problem down.
In this case, the problem is very straight forward so there isn't a lot of room for misunderstandings:
* We have to add up two numbers to get a sum
* Sum up every number combination
* Find which of those sums are equal to the given sum

# Naive solution
After we properly understood the problem, the next step is trying out a naive solution, the most obvious solution that comes to mind. A naive solution is usually very inefficient and might not be very useful in practice, but its a good way to deepen your understanding of the problem, and its easier to get where we want after we have a foundation to build upon.

Now, lets try coding a solution for our example. I will be using javascript:
```js
function twoSum(array, goalSum) {
  const solution = [];
  for(let i = 0; i < array.length; i++ ) {
    for(let j = i+1; j < array.length; j++ ) {
      const sum = array[i] + array[j];
      if(sum === goalSum)
        solution.push([array[i], array[j]])
    }
  }
  return solution;
}

console.log(twoSum([3, 5, 2, -4, 8, 11], 7));
```
Here I just add up every possible combination of numbers together and then check if they are equal to the given sum.
The time complexity for this solution is O(n<sup>2</sup>). Let's see if we can do better.

![distressed man](https://dev-to-uploads.s3.amazonaws.com/i/hlxejhnqsx90jzc3y7gm.jpg)

# Improving on the naive solution
There could be different ways in which we could improve on a solution. In some cases speed is the most important, in other cases you have to worry about memory. Sometimes its also better to go for a more readable solution than a cleaver, efficient one, it all depends on what you need.
Keep your goal in mind while looking for a solution. Sometimes you might want to go over multiple different solutions and pick the one that suits your goal the best.

In this case I'm going for speed. Here is the code:
```js
function twoSum(array, goalSum) {
  const set = new Set();
  const solution = [];
  for (let i = 0; i < array.length; i++) {
    const targetNumber = goalSum - array[i];
    const condition = set.has(targetNumber);
    if (condition) {
      solution.push([array[i], targetNumber]);
    }
    set.add(array[i]);
  }
  return solution;
}

console.log(twoSum([3, 5, 2, -4, 8, 11], 7));
```
In this solution I'm using a [`Set()` object](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set) to store and lookup values.
Steps:
1. I subtract the target sum with an element of the array
2. I use that number as a target for the `set.has()` lookup
3. If the number is inside of the set, then we have a pair which we can push to the solution array.
4. The current number of the array is added to the set. Its added after the lookup to ensure there are no duplicate pairs and to make the lookup faster since it slowly grows instead of having every element inside of it from the start
5. Once I repeat those steps for every item of the array, I return the solution array.

For this solution the time complexity is O(n) because we have to run the algorithm once for each item of the array. In the naive solution all items were compared with each other and that resulted in its O(n<sup>2</sup>) time complexity.

![thumbs up](https://dev-to-uploads.s3.amazonaws.com/i/bqxgqxu4jtaa1ini25da.jpg)
# Thank you for reading!!
This was my first post here, I hope it wasn't too horrible :)
Feedback would be appreciated.