Thinking through Algorithms

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