Interview Cake

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

I like parentheticals (a lot).

"Sometimes (when I nest them (my parentheticals) too much (like this (and this))) they get confusing."

Write a method that, given a sentence like the one above, along with the position of an opening parenthesis, finds the corresponding closing parenthesis.

Example: if the example string above is input with the number 10 (position of the first parenthesis), the output should be 79 (position of the last parenthesis).

We can do this in time.

We can do this in additional space.

How would you solve this problem by hand with an example input?

Try looping through the string, keeping a count of how many open parentheses we have.

We simply walk through the string, starting at our input opening parenthesis position. As we iterate, we keep a count of how many additional "(" we find as openNestedParens. When we find a ")" we decrement openNestedParens. If we find a ")" and openNestedParens is 0, we know that ")" closes our initial "(", so we return its position.

using System; public static int GetClosingParen(string sentence, int openingParenIndex) { int openNestedParens = 0; for (int position = openingParenIndex + 1; position < sentence.Length; position++) { char c = sentence[position]; if (c == '(') { openNestedParens++; } else if (c == ')') { if (openNestedParens == 0) { return position; } else { openNestedParens--; } } } throw new ArgumentException("No closing parenthesis :(", nameof(sentence)); }

time, where n is the number of chars in the string. space.

The trick to many "parsing" questions like this is using a stack to track which brackets/phrases/etc are "open" as you go.

So next time you get a parsing question, one of your first thoughts should be "use a stack!"

In this problem, we can realize our stack would only hold '(' characters. So instead of storing each of those characters in a stack, we can store the number of items our stack would be holding.

That gets us from space to space.

It's pretty cool when you can replace a whole data structure with a single integer :)

Reset editor

Powered by qualified.io

. . .