Problem

/** 
 * Given an @param input string, and an opening parenthesis @param openingIndex,
 *   return the corresponding closing parenthesis index if any (or return `null`)
 * Example: 
 *  `Betty (had (a bit) of butter (but the (butter))) was bitter`
 *   input ^                          should return ^
 */
export function getClosingParenthesis(input: string, openingIndex: number): number | null {

}

Solution

/** 
 * Given an @param input string, and an opening parenthesis @param openingIndex,
 *   return the corresponding closing parenthesis index if any (or return `null`)
 * Example: 
 *  `Betty (had (a bit) of butter (but the (butter))) was bitter`
 *   input ^                          should return ^
 */
export function getClosingParenthesis(input: string, openingIndex: number): number | null {
  if (input.length <= openingIndex) throw new Error('Out of bounds opening index');
  if (input[openingIndex] != '(') throw new Error('No parenthesis at opening index');

  let nestedOpened = 0;
  for (let index = openingIndex + 1; index < input.length; index++) {
    const char = input[index];
    if (char == '(') {
      nestedOpened++;
    } else if (char == ')') {
      if (nestedOpened == 0) {
        return index;
      }
      nestedOpened--;
    }
  }

  return null;
}

Transcript

00:00

Scoring interviews go. Today's is not particularly challenging, but it is my preferred form of question where it is not testing you for some magical intuition and instead focuses on basic programming skills. So let's jump in and have a look. Here we have a very basic problem statement. Given an input string and an opening parenthesis index, we have to return the corresponding closing index, if any, otherwise, we will return now. Now, as we've mentioned before, when starting out, if an example is not given, it's a great idea to verify our assumptions by writing down an example. Here we have an input string

00:34

and given an index pointing to the first bracket, we should return the corresponding closing bracket. The key thing to note over here is that between the opening and the closing, there might be multiple nested opening and closing sections. For example, a bit is one section, but the butter is one section, and butter itself is another section. Now let's start writing code. Based on the things that we know, we are going to have a function that is going to take an input string and an opening ES index, and then we'll return a closing princess index if found. Otherwise, it'll return now.

01:08

Now, before we start fleshing out the body with the actual search, we are going to write the worst case scenario where nothing is found by simply returning. Now that's one case handled. Now let's take a step back and think about the search we have to return when we find a closing bracket, but only if the number of closing and opening brackets between our start and end matches up exactly. We create a variable to maintain this unclosed opened nested index, and then start our loop at the opening index plus one and terminate before the end of the string. And in each iteration, look at the current character.

01:43

Now, if this character is an opening es, then we've essentially started a new nested section and we incremented the nested open count. A device fits a closing Es, and we don't have any nested open sections. Then congratulations, we found a closing index. Otherwise, we are simply closing off an already opened nested section, and that is it. As you can see, it's a bit of code, but it's quite simple. There's nothing magical about it, but it tests a few simple concepts. For example, your ability to maintain account of opened and closed S

02:14

and your ability to loop through a portion of a string effectively. In terms of space complexity, we are not maintaining anything beyond the input string, so it is a constant O of one. And in terms of time complexity, we are simply looping through the string, potentially all the way till the end. So it's linear time or OFN. Now, as an added bonus, just to set yourself apart from the competition, you can start handling exceptional cases. For example, if the opening index is greater than or equal to the input string length, then it is clearly out of bounds and you can throw a new error. And another exceptional case

02:47

that you can potentially talk about is if the opening index does not actually point to an opening premises.

Account Required

Coding Interview Lessons

Bracket Matching

Sign in to access this content

Problem

Solution

Transcript

Coding Interview