This Algorithm Will Make You $163,000
Like anyone who has ever connected to the internet, I’ve had my fair share of wasting time. When it come to YouTube there is no better place to casually waste hours of your precious life. While on the all consuming YouTube, I came across a video that was super interesting and I would later realize that it would make for a great blog post.
The video was about a Google interview where a candidate had to solve an algorithmic problem that was constantly changing as he solved it. As the video went along I would pause the video and do my best to solve the problems being presented. So for this blog post I will go through the different solutions in Ruby and why they are so effective.
arr1 = [1,1,3,6]
arr2 = [1,2,3,6]
Sum = 8
The first problem that was given was to write a method that would go through an array of sorted numbers, and the method had to see if any two numbers in the array would add up to eight. If there was it would return the numbers, otherwise it would return a blank array.
Getting The Job Done…Kinda
The first solution which is very obvious is to loop through the array and go number by number checking if its pair is there. The solution might look like this:
The problem is that this solution is extremely slow. If you had millions of numbers this method would take way too long.
The job can get done, but not really. Time to optimize.
The question arises, can we get all solutions by just going through the array once? This would be the solution we are looking for.
The solution to this is actually pretty clever. Here’s how it works:
The reason this solution is so much more efficient is that the method only loops through the array once a O(N) solution. In the previous method, the amount of time that method would take is much higher as it is not linear a O(N²) solution.
The way this works is that it starts with the highest value and lowest value, and checks to see if they are larger than the sum we are looking for, in this case eight. If it is larger, the upper value moves to the second largest value in the array and keeps going until the sum of the two numbers are below the sum we are looking for. After that, if the sum is not reached, then the lower value moves up to the second lowest value. This continues until a pair is found or the whole array has been checked.
The new trick the interviewer throws is that we have to take in an array that is out of order. You might think, just implement the sort method and then use the same solution as above. The problem with this is that the sort method is not very efficient if we are using a large dataset.
The best solution to implement would be this:
What this does is creates an array that will hold the differences between a value and the total we are looking for. The method loops through each value in the array and checks if the value is equal to a value in the new array (made up of differentials). If the value is found, that means that there are two values that add up to the total we are looking for and returns them.
If the value isn’t found, meaning it has no pair, its own difference with the sum is added to the differential array.
The reason this is efficient is that it only goes through the original array once making it an O(N) solution. It also ensures that there are no false positives if the differential is equal to the value. An example of this would be looking for the sum of 6 and having an array such as [1,3,1,4]. If the method did not create a new array and just checked for a differential in the original array it would return true because the value of 3 also has a differential of 3.
Overall this was a great exercise to get into simple algorithms and prime the mind to think in more efficient ways.
Good luck with your new job at Google!