JS Interview Problems: Rock, Paper, Permutation

For those of us who are entering the job market, knowledge of how to slay a toy problem is crucial. They are a demonstration of both your technical prowess and thought process to potential employers, which is why you should (if you haven’t already) start practicing. The problem on the docket for today is one that can be a bit of a headache if you aren’t accustomed to recursive concepts, but with a little study and practice it will become a part of your JavaScript algorithm arsenal. It’s known as “Rock Paper Permutation” and it goes like this: Given a number of rounds (n), return all of the possible play combinations for “n” number of rounds. Let’s begin.

We will start by breaking down the problem with O.I.C.E. which is an acronym that stands for Outputs, Inputs, Constraints, and Edge Cases.

O: For this problem our output will always be an array of strings →

Ex. Output for two rounds: [‘rr’, ‘rp’, ‘rs’, ‘pr’, ‘pp’, ‘ps’, ‘sr’, ‘sp’, ‘ss’]

I: Our input will always be a number (n) that represents rounds to be played

C: We will assume there are no constraints

E: Just be mindful of an input value of zero or a really high number as it may blow the stack.

With O.I.C.E. done, we now have a clearer picture of what is expected of us when working through this problem. We can start by declaring a function that accepts a single parameter. Inside the function we can initialize an array to store the possible play combinations to be returned at the end along with an array that holds the string values that represent the play options i.e. “r”, “p”, and “s”. We also know that an input of “0” will return an empty array, so with this knowledge let’s get a basic setup going.

Okay, that looks like a pretty good start, now we can start to build out our recursive subroutine. Now let’s give some thought to a base case. We know that in order for an outcome to qualify as a “result”, the length has to equal the number of rounds. So for example if the input were three the output would look like “[‘rrr’, ‘rrp’, ‘rrs’, ‘rpr’, ‘rpp’, …etc.]” and the length of all of the results would need to be three. The same rule applies to any number as the input. With this in mind, our base case needs to occur when the length of the argument to our subroutine is equal to the number of rounds, then that result needs to be pushed into our results array.

Cool, now we are almost done! The next phase is the real meat of the problem. I am sure you have noticed that we kick off our subroutine with an empty string. We are going to iterate through our play options array and concatenate each possible play option onto the string until it becomes the same length as the number of specified rounds. This is accomplished by calling our recursive function on each element in the options array until it meets the base case. Once we hit our base case we need that return statement on line 8 to kick us out of that stack frame so that we can move on and begin to build up the next permutation string. If it is hard to visualize don’t fret, that’s normal; try diagramming out a tree structure to help grasp the process. Our end result looks like this:

There you have it! The rock, paper, permutation. The solutions to toy problems have a tendency to look remarkably easy once you see them. This will be the first of many JS interview problems to come and I hope you enjoyed this one!