Test Driving 4 String Algorithms in Ruby

I’ve been working my way through Cracking The Coding Interview and found the practice problems useful. Here are 4 of them with spec examples. I encourage you to try copy the tests and try the examples out before looking at the answers. You can find the full set of specs on github.

  1. Design a method to determine if a string has all unique characters.

Let’s start with some basic tests for a truth case and a false case.

Now let’s talk about the implementation. Remember to try out the implementation before checking out this one.

This method builds a hash map of letters, with the character being the key and a boolean or nil. As it iterates over the input string, the hash map for each character gets assigned to true, and the loop breaks on the first case of an repeating key value pair.

  1. Reverse a string (without additional data structures).

Let’s again start with tests for reversing a string.

Now for a basic implementation,

Ignoring the fact that ruby has a built in reverse method, this version is not ideal because it introduces a new string. Below is a version that reverses the string characters in place.

It simply swaps characters starting with the first and last pair and working its way towards the middle of the string from either end.

  1. Write a method that determines if 2 strings are permutations. Again, let’s start with some tests of the method’s desired behavior.

And now for the implementation,

In 3 steps, this method breaks the first string into an array of it’s characters. It then deletes each character in that array as it finds the character in the second string. It then checks if character array is empty.

  1. Write a method that compresses a string based on the counts of repeated charaters. For example,

Here is an implementation that iterates over the input, alternating between incrementing the count and resetting it while building up the output string.

Incrementally test-driving aglorithms is a useful way to break down a problem into smaller parts. It’s also a perfect opportunity to translate the english of a coding problem into working code, which verfies understanding of the problem and goal. Hopefully this is useful to you as a process when practicing coding interview questions.

See all posts »