CodeSignal — Reverse In Parentheses

Today we are going to solve the test from CodeSignal reverseInParentheses, we will take a look at the test from different angles and shows different solutions in javascript.

If you haven’t tried the test yet, please go to CodeSignal and try the test before reading, it will be more interesting that way, always try to solve the test before looking at the solutions 😇.

*The full solution is at the bottom of the post*

The code is written in Javascript, but it will be simple enough that you should understand it easily even if you're not a Javascript developer.

You can read the instructions below or on CodeSignal, the task is pretty simple, get a string with parentheses (possibly nested) and reverse the text in the parentheses, but without the parentheses — there are some nice examples for that.

The code starts with an empty function, which recieves a string.

function reverseInParentheses(inputString) {
  // TODO
}

Let us see what we actually need to do:
1. Find the pairs of parentheses
2. Find the part of the string we need to reverse
3. Reverse the string
4. Repeat until all parentheses are replaced

Find the pairs

Seems simple enough, so for the first part we can do 2 things, either loop over it as an array of characters, or use Regular Expression (regex) since we are working on a string, lets start with the regex part — I love using https://regexr.com when I need to use regex, because honestly… Who remembers all the regex rules by heart 😅 ??
Regexr will allow us to test and will inform us what each part of the regex is doing:

\( : will match a starting parenthesis “(”
[a-zA-Z] : will match english letters
*? : will match any number of characters, but the question mark will match the shortest amount of characters, got when there are a few pairs that need to be matched individually.
\( : will match an ending parenthesis “(”

In order to implement it by code, we can execute the regex we made on the string, if we didn’t get anything then there is no parenthesis to match, if we did, we can get the startIndex which indicate the open parenthesis, and the end index which indicates the location of the closing parenthesis.

function getStartAndEndIndexes(inputString) {
  const regularExpression = /\([a-zA-Z]*?\)/;
  const execData = regularExpression.exec(inputString);
  if(!execData) {
    return null;
  }
  const startIndex = execData.index;
  const endIndex = execData.index + execData[0].length - 1;
  return {startIndex, endIndex}
}

The other option will be for us to use a loop — honestly, in an interview, I would rather use a loop since I do not trust my knowledge of regex, all we want to do is the same thing, but with a loop, I will not use array functions, to keep the code simple and also because I will be using a break which doesn’t exist in the array functions.

We are initiating variables, startIndex will indicate the location of the open parenthesis, and the endIndex will indicate the location of the closing parenthesis, do notice we keep updating the start until we meet the first end because in case of something like foo(bar(baz))blim we want to first reverse (baz), and only then reverse the (bar(baz)) part.
Once we find a closing parenthesis we can break out of the loop, and make sure we found a parenthesis, if we didn’t we can just return the string with no changes.

function getStartAndEndIndexes(inputString) {
  let startIndex = null;
  let endIndex = null;
  const chars = inputString.split('');
  for(let i = 0; i < chars.length; i++) {
    const c = chars[i];
     if(c === '(') {
       startIndex = i;
     }
     if(c === ')') {
       endIndex = i;
       break;
     }
  }
  if(startIndex === null || endIndex === null) {
    return null
  }
  return {startIndex, endIndex}
}

Find the part of the string we need to reverse

This one is simple, we just need to use a substring to get the parts that we wish to replace, we can also remove the parenthesis at this point since we don’t need them (that is why we add +1 to the start and end indexes).

function reverseParentheses(startIndex, endIndex, inputString) {
  // before the parenthesis
  const startSegmant = inputString.substring(0, startIndex);
  // the parenthesis
  const parenthesisSegmant = 
  inputString.substring(startIndex +1, endIndex);
  // after the parenthesis
  const endSegmant = 
  inputString.substring(endIndex + 1, inputString.length);
  return startSegmant + reverse(parenthesisSegmant) + endSegmant;
}

Reverse the string

To reverse a string in javascript we can simply do this:

function reverse(string) {
  return string.split('').reverse().join('');
}

That being said, in lots of interviews the interviewers don’t like you using native functions 🙄, so here is a solution with a loop… these two code snippets will work the same way.

function reverse(string) {
  let newString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    newString += string[i];
  }
  return newString;
}

Repeat until all parentheses are replaced

Here is where we are kind of at the mercy of the interviewer, we can either use a loop or a recursion, I for once hate recursions, I believe it can cause confusion, but pretty much anyone who studied computer science in college just loves it so much…

So let’s start with the recursion, we are simply calling the functions we already created, we introduce the break statement when we check if there are indexes, and we keep calling the same function with the new value until it will hit the break statement.

function reverseInParentheses(inputString) {
  const indexes = getStartAndEndIndexes(inputString);
  if(!indexes) {
    return inputString;
  }
  const {startIndex, endIndex} = indexes; 
  const newString = 
  reverseParentheses(startIndex, endIndex, inputString);
  return reverseInParentheses(newString);
}

And the loop version of this would be using a while loop to achieve the same thing.

function reverseInParentheses(inputString) {
  let indexes = getStartAndEndIndexes(inputString);
  while(indexes) {
    const {startIndex, endIndex} = indexes; 
    const newString = 
    reverseParentheses(startIndex, endIndex, inputString);
    inputString = reverseInParentheses(newString);
    indexes = getStartAndEndIndexes(inputString);
  }
  return inputString;
}

Wrapping it up

This test is quite nice, it can be solved in multiple ways, it’s not very complicated but not too easy either, it shows an understanding of working with strings and arrays.
I have made the solution quite long, it is on purpose, even if I can write it all in 3 lines I do not want to, I rather have the code simple and organized rather than short, complex, and confusing.

Full solution:

https://gist.github.com/liron-navon/2e6a05aa80a6121c23dbb6a832eb15a8