Interview Questions

September 26, 2016

This is the second article in series about programming interview questions and how to think through and solve them! If you want to start from the beginning, check out even occurrence!

This article is covering a very common interview question, all permutations of a set. *‘Implement a function that gets all permutations or orderings of a given string. For example if the input is ‘abc’, the output should be [‘abc’, ‘acb’, ‘cab’, ‘cba’, ‘bca’, ‘bac’].*

A lot of people hear the word permutation and get scared, so let’s first tackle what a permutation actually is.

*A **permutation** relates to the act of **arranging** all the members of a **set** into some **sequence** or **order**.*

Easy! Well.. not quite, but at least we now know what we need to return at the end. That is, if we’re given ‘abc’; the result should be:

*[ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']*

Let’s first take a look at how this problem might naturally be solved. If given ‘abc’, I would naturally separate the first letter and find all permutations of the next two letters. So for “abc” I would have:

In this case, my mind jumps straight to recursion because we don’t know how large the string will be in our test cases. So for all letters in the string, we can grab one letter of the string and prepend it to all of its permutations without the letter in it. In recursion we need our ‘base case’ when we want to stop our recursive call. In this case it will be when the string is a single character, we’ll return the character.

The time and space complexity of the above algorithm should be the same as the number of items produced. The number of unique permutations of any set of size *n* is *n*!, therefore the time and space complexity of our algorithm is O(n!).

Having worked across sites raking in over 50 billion website visits annually, *Michael Mitrakos** can help your business to crush the web game with an award winning website.*

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!