Interview questions: verify the braces

This is one of the easier coding tasks, but you still can meet it in some preliminary tech screening. The problem looks like this:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Description taken from Leetcode (c).

How do you solve it?

We have been using this task for the tech screening. What is interesting is that how many people don’t really know how to deal with this (and mind you, this is an “Easy” category on Leetcode). Some people try to use regular expressions; some try to think up a brute-force solution going through the string and counting the opening and closing brackets. If you think about it, though, you will understand, that neither will suffice. For example, how can counting help with the easiest case of ([)]?

The solution that should jump to your mind, but may not if you never trained to solve coding problems, is a stack. Why the stack? Well, because the pair of braces or brackets can only be checked for completeness when you see a closing bracket; but that means that the opening one should be kept somewhere waiting and be on top of some data structure to check. And the structure which allows LIFO access is a stack. Happens that we have a ready-made Stack class in Java.

So, how does the simple solution look like?
Basic idea is, you start walking through the string. If the symbol is one of opening ones, you push it into a stack. If it’s closing, you peek into a stack and see if it’s a match. If yes, you pop it from the stack. You return true if the stack is empty in the end.

Is there any other way to solve this? What if the stack doesn’t come up to your mind?
As always, there’s more than one way to solve a problem. Let’s look at this example: ([]){}.

Let’s try to replace correctly matched pairs:

“([]){}”.replace(“[]”, “”) => “(){}”.replace(“()”, “”) => “{}”.replace(“{}”, “”) => “”

So, we can just loop through the string replacing “{}”, “()” and “[]” with an empty string. When the result becomes empty, it means that all pairs are matched. What if it doesn’t become empty; how do we break from the cycle? Well, we need to check if the length of the string has changed after a round of replacements. If it hasn’t, then we break.

This looks even better; simple and readable, but is it better in truth? I’d say that no, not really. Why? Well, because the String class is immutable, and therefore every time we do that s.replace() we are creating a new string object on the heap.

So, how best to do that? Could we rewrite the code using the StringBuilder class? Well, not directly, because it doesn’t have a replaceAll method. You’d have to write it yourself using an existing replace method. There’s a StrBuilder class in Apache Commons library which does have this method, but it’s not a standard Java class, you’d have to add a dependency.

So, even this simple task can give some food for thought. For the interview, however, any of the solutions will do. If the stack isn’t the first thought in your head, you can do without.

Advertisements

About Maryna Cherniavska

I have productively spent 10+ years in IT industry, designing, developing, building and deploying desktop and web applications, designing database structures and otherwise proving that females have a place among software developers. And this is a good place.
This entry was posted in interviews, java, Programming, Uncategorized and tagged , , , . Bookmark the permalink.

4 Responses to Interview questions: verify the braces

  1. eyalgo says:

    The replace solution is very nice and elegant.
    It wouldn’t work if you allow in the input other characters.
    Example: (AB[ccx]){yGf}

    Also, I wonder how it can be implemented using Java 8 features, instead of do-while loop.

  2. I was looking at some of your blog posts on this internet site and I believe this website is real instructive! Keep on posting.

  3. There’s not much better than a well authored article! Thank you
    so much for this relief,I loved every second of the read.
    Will be looking forward to your next article 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s