Coding Challenge: Matching Parentheses

Coding challenges are not only a fact of life for technical interviews and assessments, they are also fun! Mastering the process of solving coding challenges will give you the confidence to go into any technical interview or assessment and succeed. And we all know confidence is half the battle when interviewing. In this series, I am tackling various coding challenges and explaining my process along the way. For this challenge, I am using Javascript since that is my primary focus these days.

The Challenge: Matching Parentheses

The Matching Parentheses challenge is one of the most common challenges on assessment and technical interviews. It is a relatively easy challenge so make sure you have this one down.

Given a string and the symbols "(" and ")", write a function that will determine if the symbols are properly nested in the string (all opening symbols have closing symbols).

Time Management

Time management is an important aspect of interviews and assessments and should be taken into consideration right from the start. It is better to have completely coded correct answers to all the challenges than to have one perfect answer and the rest unfinished. For that reason, I usually start with the "brute force" method. Just get a solution down. Worry about efficiency and elegance later. And yes, Big $\mathcal{O}$ considerations come after we get through the brute force phase.

Brute force

Let's just brute force this puppy:

function hasMatchingSymbols(checkString) {
  let openParens = 0;
  for (let char of checkString) {
    if (openParens < 0) return false;
    if (char === '(') {
      openParens += 1;
    } else if (char === ')') {
      openParens -= 1;
    }
  }
  return openParens === 0;
}

console.log('hasMatchingSymbols: ', hasMatchingSymbols('(here we (go))()'));

Simple enough. We are counting the number of opening parens and subtracting when we find a closing parenthesis, making sure to bail if we find an closing parenthesis without a previous open (our counter goes negative). At the end, we just make sure we are at 0 on our parens count.

Refactor

Our brute force version has a Big $\mathcal{O}$ of $\mathcal{O}(n)$. Not bad. Let's make it a bit more generic since the challenge implies the symbols could be generic and not just parentheses. Let's also take this opportunity to add some comments for future devs (the reviewer). Comments aren't usually necessary in an assessment since the software usually doesn't look at anything but the results.

function hasMatchingSymbols(checkString, openSymbol = '(', closeSymbol = ')') {
  // avoid logical errors
  if (openSymbol === closeSymbol) {
    throw new Error("Open symbol and close symbol must be different.");
  }
  // keep running total of open symbols
  let openSymbols = 0;

  for (let char of checkString) {
    // if we go negative, then we have a dangling close symbol
    if (openSymbols < 0) return false;

    if (char === openSymbol) {
      openSymbols += 1;
    } else if (char === closeSymbol) {
      openSymbols -= 1;
    }
  }
  // anything but zero here is a false result
  return openSymbols === 0;
}

console.log(
  'hasMatchingSymbols: ',
  hasMatchingSymbols('(here we (go))(', '(', ')')
);

I don't really see the need for any further improvement on this one, let's go ahead and submit.

Conclusion

This was another relatively easy coding challenge, but it does appear quite often. Make sure this is in your toolbox using your favorite language.

See Also

• Github Repo: Matching Parentheses
• Github Repo: Coding Challenges