Ruby Algorithms - Moving Past the Basics

After figuring out the archetypal intro algorithm - the palindrome problem - I thought I would be ready to take on any coding interview. I could pseudo code, I could talk through the solution, and I could think about variants on the problem. Then I started to look through Cracking the coding interview, and I realized I was completely over my head. The problems in the book are in the major league, and I'm still playing t-ball in the backyard.

Luckily, there is this wonderful place called the internet, where many people were willing to give advice on how to get there. Having a strong grasp on your language of choice will be the starting point. I'm most comfortable with Ruby, so that will be the language we go over. I'll be assuming that you've already been exposed to a few algorithms, but you are looking to start working towards the next level. (As mentioned before, you should have worked through the palindrome problem). Ruby is a very user friendly language; It has a method for almost anything you could ever think of.

Algorithmic Thinking in Ruby

To start, let's talk about the basic approach to solving an algorithm. This is a model that I usually follow:

1. Read the Problem

2. Understand what is required for the inputs and outputs

3. Identify in plain english/pseudo code what steps will be needed (what algorithm)

4. Map the pseudo code to ruby processes and concepts

5. Write Code

6. Test

7. Optimize for time and space

Now lets look at a basic algorithm, and apply these steps:

Write a function that will find all the anagrams of a word from a list. You will be given two inputs: a word and an array of words. You should return an array of all the anagrams, or an empty array if there are none. For example:

 anagrams('racer', ['crazer', 'carer', 'racar', 'caers', 'racer']) => ['carer', 'racer']

1. Read The Problem: The question is asking us to find all anagrams for a given word from another list of words. An anagram is a word that is composed of the same letters as the given word.

2. Understand what is required for the inputs and outputs: They are giving us two inputs, a string, and an array of strings. They want us to return values from the array in a new array.

3. Identify in plain english/pseudo code what steps will be needed: This is the tricky part. First, we know we need to iterate through the array of potential anagrams and compare them to the target word. If they are an anagram, we will put those words into a new array. Since we know that the anagrams will be composed of the same letters just in different order, we need to find a way compare just the letters, without order. Sorting comes to mind for that.

4. Map the sudo code to ruby processes and concepts: For the iterator, we are selecting elements from an array so let's use select. For our boolean statement, we want to compare the sorted target word with the sorted element in the array. To sort, we want to sort by chars, so we can use .chars and .sort. If they are equal, then select that element. .chars will treat a string like an array, and .sort sorts it by the character values.

5. Write Code:
   

   def anagram(word, words)
       sorted_target_word = word.chars.sort
       words.select { |word| sorted_target_word == word.chars.sort}
   end
   

6. Test: Our example passes (trust me)!

7. Optimize for time and space: For this example, we weren't looking to optimize. But if we were... the sorting will take some extra time, which should be noted if you were looking to optimize. Sorting takes O(mlog(m)) time (ruby uses quicksort), where m is the number of letters in each word. This multiplied by the number of words, n, gives us n*m*log(m). This might not be most efficient algorithm for this process. Ruby does a lot of work under the hood, so it is easy to forget to think about time and space. A trick that could be useful, if our words were very long, and we had a lot of them, is creating a hash map. You can create a hash of the target word by using target = Hash.new(0) and then word.each {|char| target[char] += 1}. For each word in the array you can compare their hash map with the target hash map. Each map takes linear time to set up, and we have to go through the array once, leading us to about O(m*n) time. This is still linear time. Consider that the total operations done on each letter is one constant time insertion into the hash map, and then one constant time comparison with our target word. Hence O(n) time, where n is the number of letters in the word array.

Side note - Memoization

Memoization is where you store expensive function calls to be used later to save time in a computer program. While the hash we are using above isn't quite that concept, it starts exploring the potential of using hashes in algorithms. The easiest example to explain memoization is for factorials. When you want to complete 5!, if you already know 4! then its only a two step process ( 5*4!) . Otherwise, you will have to call 5*4*3*2*1, which can take a lot more time!

Tips for Better Solving

The steps for algorithmic thinking will only start working for your with lots of practice. I recommend starting on codewars or another similar site. Code wars has different levels of algorithms so you can start where you are comfortable.

In Ruby, there is a built in method for many common algorithm problems, like sorting and finding in an array. While it's fine to use these in practice, it's also important that you understand how these work. I encourage everyone who is interested in becoming better at algorithms to start thinking through each question, rather than memorizing solutions.