# Thinking through Algorithms

### nwdunlap17 ă»8 min read

## Your Brain is Too Smart for Simple Algorithms

I imagine most people want to start programming for the same reasons I did. Growing up, I thought computers were these brilliant things that could simulate entire worlds, learn how to solve puzzles, and hold millions of books worth of information. And that made it really hard for me to realize one very basic truth about programming. Computers are *morons*.

This truth is one of the most common hurdles for new programmers. They see a relatively simple algorithm and they donât even know where to start. It isnât that theyâre too stupid to find the solution, the problem is that theyâre too smart to see thereâs a problem at all!

Here is one of the simplest algorithms in the word. Whatâs the largest number in the following list?

3, 7, 4

Itâs seven. Obviously itâs seven. If I asked you how you know it was seven, youâd probably look at me like I just asked you what color the sky is. You just *know* its seven from looking at it! And thatâs the problem, your brain is so smart, it just skips over all of the work it did and gave you the answer. But computers are morons, and it canât do what you can do. One of the first steps of algorithm design is training yourself how to think at a lower level. Ask yourself âHow do I know that?â enough times, and eventually youâll be reach a level the computer will understand. (Assuming you donât veer off into philosophy, thatâs Descartesâ territory).

Hereâs the same question again, find the largest number in the list. But this time, think about what exactly youâre doing, talk to yourself if you have to, whatever it takes to do this task as slowly as you can.

9, 1, 16, 2, 3, 7, 14, 5, 10, 15, 7, 12, 8, 4, 19, 10, 17, 8, 13

Of course, the answer is nineteen. But for a while, you were probably thinking the answer could be sixteen. You probably saw sixteen was the highest number on the left side, and then went looking for a number bigger than 16. You reached the fifteen, and in the back of your mind, whether you knew it or not, you thought âFifteen isnât bigger than Sixteen. Sixteen is still the biggest numberâ. When you reached the nineteen, the opposite happened, you knew that nineteen was the biggest number.

So basically, you remembered what the biggest number you saw was, and you checked all the other numbers against it. When you found a bigger number, you remembered that one instead. And that level of simplicity is absolutely something you can communicate to your computer.

```
biggest_number(number_array)
biggest_number = first number in number_array
for each next_number in number_array
if(next_number > biggest_number)
biggest_number = next_number
end
biggest_number
end
```

Admittedly, thatâs not too much to write home about. Finding the largest number in a list doesnât sound very impressive. But these skills are applicable to much harder algorithms. Letâs try one.

## Making Assumptions

Iâm going to give you a couple of coordinates on a 2D grid. You have to design an algorithm to determine which straight line passes through the highest number of points.

[1,3], [2,1], [3,2], [4,3]

[2,2], [2,4], [3,2], [2,3], [3,3], [2,5], [4,4]

Thatâs quite rude of me, isnât it? After all, there are infinitely many lines on a 2D grid, how on earth are you going to tell your stupid computer not to look at them all? Letâs start by drawing out the problem to see if we can wrap our heads around it.

```
| | o o
|o o | o o
| o | o o
| o | o
|___________________ |___________________
```

Thatâs a lot better! Itâs pretty easy to see that in the first graph, the right 3 points make the longest line, and in the second graph itâs the 4 vertical points. You certainly didnât need to look at every possible line to figure that out! In fact, Iâm willing to bet that you didnât even think about vertical lines while looking at the first graph.

Your eye was drawn to the points, not the whitespace. What probably happened is that your eye found two points, and *followed the line they made*. You kept track of which line had the highest number of points just like in the previous algorithm, and when you had looked at all the lines you cared about, you knew which one was the longest.

```
best_line(points_array)
for every point in points_array
for every other_point in points_array
Find the line between the points (y = mx+c)
count = 0
for every potential_point in points_array
if (potential_point is on line) {count += 1}
end
end
end
```

Your brain has evolved over millions of years to be good at finding patterns, to solve most algorithms, you just need to break down what itâs doing into simple and concrete steps. If you get into the habit of figuring out what your brain is doing, youâll be able to quickly and carefully build your algorithms.

The next part of this post is about making algorithms faster. This comes with a big caveat.

**Most of the time, the most important thing is just finding a solution.** In interviews and in applications, the most important thing is to quickly find any solution. This allows you to demonstrate your understanding to an interviewer, or to test other segments of your code. You should only be worrying about improving the performance of your algorithm after you have one that works.

## What makes an algorithm good?

There are a few criteria that algorithms can be judged on. The âbestâ form of algorithm in an application will probably heavily rely on one of these criteria. For an interview, there typically is no âbestâ answer, but good answers tend to balance the three (or at least, keep the performance across all criteria reasonable). Being able to evaluate your answer in an interview is also a huge plus, as it shows that you have a good understanding of ways you could try to improve it.

- Simplicity: How easy it is to understand the algorithm when you see it in code.
- Scalability/Speed: How long does the algorithm take to complete? And how much longer does it take to complete when you double the amount of data.
- Size: How much memory does the computer need to complete the algorithm.

The rest of this post will focus on scalability/speed. If you devise an algorithm based on the principle of âWhat is my brain doing?â, then youâll probably already have a very simple and intuitive algorithm. And significantly reducing algorithm size usually involves some very technical tricks that are specific to the language.

## Start Answering before they Stop Asking

If youâve ever watched Jeopardy, you know that the most successful contestants are the ones that are hitting the buzzer before Alex Trebek is done reading the question. Following the methods described above will help you get an answer to the problem, but they may not help you get the fastest answers. The following two problems are taken straight from Google interviews, and theyâre both about solving the problem as quickly as possible.

One of the biggest factors in algorithm speed is iteration time. How many times do you need to go through your data? When we were finding the biggest number, we only had to go through the list once. If we double the length of the list, the time it takes to find the biggest number will double. When we were finding the most populated line, we had to check every pair of points. If we double the number of points, the time taken to find the line will quadruple. Obviously, we would much prefer the former to the latter, because the time stacks up very quickly.

### Getting as much information as possible

If youâve never heard of them, linked lists are data structures where each member points to the next member. Theyâre very useful because they can be scaled infinitely, and they take up about as little memory as possible, since thereâs no overhead keeping them organized. The downside to linked lists is that they are a pain to navigate, since you can only start from the beginning and travel forward one entry at a time.

The google problem is this: find the middle node in a linked list, but you can only use a single loop. This restriction immediately prevents the obvious solution: go through the list, count the number of elements, then go through half again as many nodes to find the half-way point.

The trick here is to get the maximum amount of information from each node that we can. If we stop and consider exactly what we know at each step, we can solve this problem in a single loop. One way to do this is to assume that any node we visit could be the last node and prepare an answer for if that is true.

Letâs run through what that looks like:

We start at the first node, if this is the only node in the list, then it is the middle node as well.

When we reach the second node, the first node is still the middle node.

When we reach the third node, we know that the first node cannot possibly be the middle node. If this is the last node, the second node is the middle node.

If we reach the fifth node, the third node is the current middle node.

Extrapolating from this, every two nodes we move forward, the middle node advances by one. We can continue this pattern until we reach the end of the list, and then immediately return the middle node we have prepared.

```
Find_middle(linked_list)
fast_pointer = linked_list.first
half_pointer = linked_list.head
while (fast_pointer != null)
fast_pointer.next
fast_pointer.next
half_pointer.next
end
```

### Finding the Sum with a Hash Table

Given a list of numbers, find the pair of numbers whose sum is a chosen number.

Find the numbers that sum to 12 in the following list:

2, 5, 8, 6, -3, 14, 4, 1, 3, 12

Following a similar theory to the algorithm above, if we keep potential answers in mind, we can solve this problem very quickly. For example, the first number is 2, this means that if we ever find a 10 in the list, we can safely ignore any remaining numbers in the list, as we have already found the answer. Eventually, we will reach 4, and realize that we already have an 8, thus completing the sum.

The issue with this problem is how to compare the potential answers weâve found to our current number. If we store the potential answers in an array, then we arenât actually saving any time at all, as weâll be examining that array once for every number in the original array. Instead, we have to use a hash table.

A hash table is a special kind of data structure. Unlike an array, it is expensive to iterate through a hash, but it is very quick to check for a specific value. To solve this problem, we simply need to check if the current number already exists in a hash of potential answers, if it doesnât, add the next potential answer to the hash.

```
Find_sum(array, sum)
potential_answers = {}
For each num in num_array
if (potential_answers[num] == true) { return [num, sum-num] }
else{ potential_ansers[sum-num] = true }
end
```