Coding Interview Questions #1: Permutation of a given String

source

Introduction:

Hey ho and welcome to the first post of my series called: Coding Interview Questions. In the following weeks I'm going to talk to you through different Coding Interview Questions and how you can master them. It's pretty common for larger companies to ask those questions directly at the interview. Most of the time candidates have to highlight their thinking process and later write actual code on a whiteboard to solve the problem. I'm personally a computer scientist and I've been working as a software developer. Right now I'm finishing my masters thesis before starting my PhD at a German research institute. I had interviews at Google, Bloomberg and several less known companies. I had interships in the US, London and Madrid. I decided to come back to Germany because of my friends - Yes I'm a computer scientist with a social life ! I'm honestly not the most experienced coding monkey, but I do my best to explain you the way I solved the problems and show you my personal source code.

To sustain the coding interview process, you will have to train it. Writing compilable code on a whiteboard has to be trained and the problems you might be asked for will not be trivial at all. Personally I even had problems to solve some of them at home. So if you want to become a software developer at Google, Amazon, Facebook, etc. you gotta learn to write code on a whiteboard and you should train the questions they might ask you. 

Todays Coding Interview Question is called: Permutation of a given String.  I believe many people would mark this as an easy task, but in my opinion it's not. It's not comparable with sorting algorithms or similar, so getting the masterplan might be a bit tricky. But let's just jump right into it!

The Problem 

Input: String with length n | Output: All permutations with the same length n

Permutation is a rearrangement of the elements of an ordered list S into a one-to-one correspondence [1].  This basically means that the permutation of a word is asking for how many  distinguishable  ways you can rearrange the letters of it. Or better how many possible combinations of strings a word can have. For example the word 'STB' has the following permutations:

Mathematically the amount of permutations possible is calculated by the following formula, where n determines the length of the word and r the amount of characters involved:

  =  

As you can see above, the example already gives you all permutations of the word 'STB'.
Further information about the background of permutation can be found here.[2]

Understanding the Problem:

At this point we received all information needed to hop right into the problem and start coding it. Unless you are a freaking brainiac you will still have some questions to ask. A good question to ask would be if all permutations share the same length. The problem could also imply all permutations with n to 1 lengths. But for this time we keep it as simple as possible.

I highly recommend to ask as many questions as possible at this stage. No one even will judge you for asking the obvious ones. If you want to sustain the interview you gotta understand the problem in detail . It's always good to ask specifically for the input and the output. This time the output has to be all permutations of the word. It'd also be possible to ask for the amount of permutations or to return a specific and suitable datastructure.

If you try to code the problem on your own, feel free to ask questions in the comment section. I'll try my best to help you out.

The Solution 

In this chapter I'm going to provide you my solving process and afterwards show you my Java-implementation. I've personally worked as a Java developer and thus it's my favorite programming language. Since you need to write compilable code on the whiteboard, I also highly recommend using a language you are very handy with.

So the basic idea of my solving algorithm is recursion. I'm setting up a loop to mark characters as fixed prefix. To do so I'm swaping every character once to the beginning. This is handled with the runtime variable j. Afterwards I'm calculating the permutations for the suffix recursively. If the suffix pointer points to the last character of the word, a permutation is found and printed. At last I'm swapping the characters back again to avoid misscalculations of the prefix.

The following diagram shows which permutations are calculated within the loop.

Finally >This< is my implementation.

Also feel free to comment whether you want to talk about a specific coding problem! Thanks for reading, @belike