Computer Algorithms Explained: Learning through Spotify

If you've ever interviewed for a programming role I'm sure you've been thrown a question requiring you to remember your Computer Science Algorithm course from college, and prove you know the best sorting algorithm... and its big "O" complexity... and it's space efficiency... etc... etc...

Now (if you're anything like me), you detest those interview questions because you simply can't remember every algorithm for every different interview question. In your day-to-day, you are likely to re-use sorting algorithms from a library (if not then you seriously should get to it!) and college courses have long been erased from your memory.

With that said, knowing a few essential algorithms is a really great tool to have in your programming toolbox. Knowing how a search or sorting algorithm works will help you figure out the right solution for your use case and find solutions for seemingly unconnected troubles at hand.

Learning and memorizing algorithms is hard and frustrating. That's why whenever I teach a training course on algorithms, I always try to provide examples of where (and how) algorithms are used in a real, day-to-day apps most of us are using.

Not only does it provide a real-world use case, but any educational psychologists will tell you that attaching new information to an existing hook in memory actually retains that information much more efficiently and for a longer time.

With that in mind, I thought I'd look at four algorithms that would go into making a Spotify style desktop app.

Disclaimer: these aren't the exact algorithms Spotify uses—they're simply examples of algorithms that provide the functionalities similar to what Spotify has. Also, I don't work for Spotify... but I use these algorithms every day anyways and I am confident they will help you with your day-to-day too.

1. Sorting Artists, Albums, Song Titles

I can not think of a UI based app that doesn't use some kind of sorted data set—games have league tables, social media apps have timelines, CRM/data heavy apps have tables of sorted data, and so on.

There are a lot of different sorting algorithms out there and you almost certainly shouldn't be inventing one yourself, but a common interview question is to write a sort algorithm and comment on it's performance.

There's a huge variety of sort algorithms:

• Recursive sorts
• Stable sorts—will always return the same order for keys of equal value
• Serial or parallel sorts
• In-place sorts, which are great if memory is lacking
• Insertion sorts
• Merge sorts
• Exchange sorts
• etc...

I chose to discuss QuickSort in this tutorial because it's relatively simple but also very efficient (except for its worst case).

How does QuickSort work?

QuickSort is a divide and conquer algorithm.

So let's assume you have a list of objects representing artists and you want to sort by "Name".

var artists = ['Beyonce', 'Snoop Dogg', 'Queen', 'ABBA', 'Pharrell'];

Quicksort will pick a pivot element. This can be chosen at random or, for simplicity's sake, we will choose the first element in the array.

var pivotElement = array[0], // 'Beyonce'
    remainingArray = array.slice(1); // ['Snoop Dogg', 'Queen', 'ABBA', 'Pharrell'];

Next we'll split up the remaining list into two:

• all those who come before our first element, Beyonce,
• and all those who come after:

var less = remainingArray.filter(function (a) {
  return a <= pivotElement;
});
// ['ABBA']

var more = remainingArray.filter(function (a) {
  return a > pivotElement;
});
// ['Snoop Dogg', 'Queen', 'Pharrell']

The next step is to sort each subarray using our quicksort function recursively:

var sortedLess = quickSort(less); // ['ABBA'];
var sortedMore = quickSort(more); // ['Pharrell', 'Queen', 'Snoop Dogg'];

And then finally we concatenate all our arrays back together and return them:

return sortedLess
  .concat([pivotElement])
  .concat(sortedMore);
// ['ABBA', 'Beyonce', 'Pharrell', 'Queen', 'Snoop Dogg']

And that's it! Putting it together, our whole quickSort algorithm looks like:

function quickSort(array) {
  if (array.length > 1) {
    var pivotElement = array[0],
    remainingArray = array.slice(1);
 
    var less = remainingArray.filter(function (a) {
      return a <= pivotElement;
    });

    var more = remainingArray.filter(function (a) {
      return a > pivotElement;
    });

    var sortedLess = quickSort(less);
    var sortedMore = quickSort(more);

    return sortedLess
      .concat([pivotElement])
      .concat(sortedMore);
 
  } else {
      return array;
    }
}

Check out a full demo here

2. Simple Searches

Next, we need a way to search for Artists, Albums, etc. Now in reality the search would be powered by some kind of data store using a mixture of different indexing technologies, so the algorithm I'm about to share is not likely to be used by Spotify. However it's always important to know at least one search algorithm so that when you do need to perform some simple search in a data structure, you have a go-to algorithm ...like when someone asks you for it during an interview

As with sorting, there's a huge number of options—however, I'd like to focus on the Binary Search Algorithm.

How does Binary Search work?

A Binary Search works on a sorted data structure (luckily we just covered sorting so we know how to get our array sorted!). So let's say we want to search by artist name, like'Snoop Dogg' and our list of artists looks like:

var artists = ['ABBA', 'Beyonce', 'Pharrell', 'Queen', 'Snoop Dogg'];

First thing's first, let's define our function signature:

function binarySearch(array, valueToFind) {
    ...
}

With a binary search, we pick an element somewhere in the sorted array. If it's the one we want then great! We're done. If not then we figure out whether the value is less than the one we chose (and therefore in the left side of the array) or greater than the current value (and therefore in the array to the right).

Whichever side it's on, we then treat that as a new sub-array and search the following in the same pattern in this sub-array.

So let's see this in action. First we'll get the minimum and maximum indexes in our array, and then we'll pick our starting index (from the exact middle of the array):

var startIndex  = 0,
  stopIndex   = array.length - 1,
  middleIndex = Math.floor((stopIndex + startIndex)/2);

Now we want to see if the middleIndex contains our value. If not AND we still have values left to check then we'll check either the left or right:

 while(array[middleIndex] != valueToFind && startIndex < stopIndex){
  // adjust our start or stop index so focus on either the
  // left side or right side of the array
  if (valueToFind < array[middleIndex]){
    stopIndex = middleIndex - 1;
  } else if (valueToFind > array[middleIndex]){
    startIndex = middleIndex + 1;
    }

  // recalculate middle
  middleIndex = Math.floor((stopIndex + startIndex)/2);
}

The above code will keep looping until we find our value or the two indexes for our start/stop indices in the array meet.

Finally, we need to return the index of our value or -1 to indicate it doesn't exist in the array:

return (array[middleIndex] != valueToFind) ? -1 : middleIndex;

The final complete code looks like:

function binarySearch(array, valueToFind) {
  var startIndex  = 0,
    stopIndex   = array.length - 1,
    middleIndex = Math.floor((stopIndex + startIndex)/2);

    while(array[middleIndex] != valueToFind && startIndex < stopIndex){
      // adjust our start or stop index so focus on either the
      // left side or right side of the array
      if (valueToFind < array[middleIndex]){
        stopIndex = middleIndex - 1;
      } else if (valueToFind > array[middleIndex]){
        startIndex = middleIndex + 1;
      }

      // recalculate middle
      middleIndex = Math.floor((stopIndex + startIndex)/2);
    }
    return (array[middleIndex] != valueToFind) ? -1 : middleIndex;
}

Here's a live example: http://jsbin.com/difedon/1/edit?html,js,output

And that's how to perform a simple search across a data set. Of course we know in reality there's more to searching than that...

3. Phonetic Searches

So we now have a simple search, but no one is expected to type the exact full name of an artist to have it show up.

In fact to search for 'Pharrell', for example, most of the time I can't remember how to spell it, or I simply mistype it as 'Pharell'. I'm sure if you saw that you'd immediately think of 'Pharrell'— or "the guy that did the Happy song!", but a computer can't figure that out. Nor can the above search algorithm.

This is where phonetic searches come in handy. A phonetic search will take a String and encode by how it sounds as pronounced in English. Taking our previous example of 'pharell', 'pharrell', 'pharel', 'pharall' — these all sound phonetically very similar. So let's look at a Phonetic Search algorithm called Soundex.

How does Soundex Algorithm work?

The basic premise of a phonetic algorithms is to change the String into a phonetic hash —similar to a hash key. Then when someone types in a search string, that, too, is converted into a phonetic hash and compared to the hashes of the other strings until a match (or matches) are found.

The Soundex hash is always a letter (the first letter of the word) followed by three digits representing the remaining consonants. The algorithm to generate this phonetic hash works as follows:

1. Retain the first letter of the name and drop all other occurrences of a, e, i, o, u, y, h, w.
2. Replace consonants with digits as follows (after the first letter):

• b, f, p, v → 1
• c, g, j, k, q, s, x, z → 2
• d, t → 3
• l → 4
• m, n → 5
• r → 6

3. If two or more letters with the same number are adjacent in the original name (before step 1), only retain the first letter. Also, two letters with the same number separated by 'h' or 'w' are coded as a single number, whereas such letters separated by a vowel are coded twice. This rule also applies to the first letter.
4. If you have too few letters in your word that you can't assign three numbers, append with zeros until there are three numbers. If you have more than three letters, just retain the first three numbers.

So let's apply this to our artist 'Pharrell':

function soundex(word) {
  // first make it all uppercase
  var treatedWord = word.toUpperCase(); // 'PHARRELL'

  // Take first letter as our hash prefix
  var hash = treatedWord[0];  // 'P'
    
  // step 2. Replace consonants with digits
  var lettersToReplaceInOrder = ['BFPV', 'CGJKQSXZ', 'DT', 'L', 'MN', 'R', 'WH', 'AEIOUY'];
  lettersToReplaceInOrder.forEach(function(lettersToReplace, index) {
    treatedWord = treatedWord.replace(new RegExp("["+ lettersToReplace +"]",'gi'), index + 1);
  });  // treatedWord = '7866844'

  // update our has
  hash += treatedWord;  // 'P7866844'

  // now we have to remove duplicate numbers
  // we split the string into an array and run it through a map function
  // the map funtction
  hash = hash.split("")
    .map(function(number, index, array) {
      // if it's not the first letter 
      //     AND the previous character is a vowel 
      //     AND the previous previous character is the same as the current 
      if (index > 1 && (array[index - 1] === '7' && array[index - 2] === number)) {
        // do nothing... this counts as two identical characters next to each other
      } 
      // else if this is the first character
      //     OR the previous character did not match this character
      else if (index === 0 || (array[index - 1] !== number)) {
        // then return it
        return number;
      }
    }).join("");  // hash = 'P78684'

    // ALMOST THERE!
    // Now we just need drop out vowels, non word characters and trim to 4 or less
    hash = hash[0] + hash.substring(1).replace(/[78\W]/gi, ""); // 'P64'
    hash = hash.substring(0, 4).trim();

    // Now we have to make sure the length is 4
    // if not then pad it with 0
    while (hash.length < 4) {
      hash += '0';
    }

    return hash; // 'P640'
}

Ok, that seems like a lot of code and realistically, I probably won't remember it all in an interview. But if I were interviewing a candidate and they started talking about Soundex and how you convert the string into a hash based on consonants, remove vowels, etc., then I'd be super impressed!

So let's see if this works for our other variations of 'Pharrell':

soundex("pharrell");   // 'P164'
soundex("pharrel");    // 'P164'
soundex("pharell");    // 'P164'
soundex("pharel");     // 'P164'
soundex("pharall");    // 'P164'

And here we can see that all our variations of 'Pharrell' match!

Here's a real example with a bigger list of artists: http://jsbin.com/rohidut/1/edit?html,js,output.

4. Shuffle

Now what is any great music player without a shuffle mode? Apple even had an iPod named after it!

In theory, shuffling may seem pretty simple, but ask someone to write an efficient shuffle algorithm and people freeze up. So let's look at how we can shuffle our playlists using "Fisher-Yates Shuffle"

How does the Fisher-Yates Shuffle work?

The Fisher-Yates Shuffle is surprisingly simple. In essence, you take an array of values and choose a random one each time and place it in your shuffle pile until there are no more left.

Try to picture this with a deck of cards.

To shuffle the deck using Fisher-Yates, you'd start with the entire deck on the left side of the table and an empty space to the right. Then you pick one card at random from the deck on the left and place it on the right, repeating the process until there are no more cards on the left.

Now in programming terms, we could do the same with an array. We'd have our source array of items and remove a random one each time and place it at the end of our shuffle array until our source array is empty. However, the downside of that is that it uses an extra array. A common implementation of the Fisher-Yates shuffle does this movement inplace in the source array. Let's see a simple implementation:

function shuffle(array) {
  var nextInsertIndex = array.length, // end of the array - use to indicate where insert the shuffled item
         temporaryElement, // variable to hold the element at nextInsertIndex and swap with the random  element
         randomElementIndex; // hold's the random index

  // While there are still elements to shuffle… we decrement this until we reach the start of the array
  while (nextInsertIndex--) {

    // Pick a random remaining element from the front of the array
    randomElementIndex = Math.floor(Math.random() * nextInsertIndex);

    // now swap
    temporaryElement = array[nextInsertIndex]; // hold our element from the insert index
    array[nextInsertIndex] = array[randomElementIndex]; // put our new random element there instead
    array[randomElementIndex] = temporaryElement; // and put our temporary element where the random was removed from
  }

  return array;
}

That's all there is to it! Mike Bostock (of d3.js fame) has a great indepth article with animation showing the various implementations of Fisher-Yates. I highly recommend it to see a visual representation of what's happening.

Wrapping Up

So we've looked at four very useful and productive algorithms that go into an app like Spotify. I hope that seeing them in a fun context you can relate to will make them easier to remember (for longer)—and to actually put them to work!

What other app's algorithms would you be interested in seeing? Let us know in the comments.

Other tutorials you might be interested in:

• Introduction to Greedy Algorithms
• Two Algorithms for Solving Vigenere Cipher in Ruby
• How to Optimize Your Code for Interview Questions