MongoDB Interview Question: Given a set of open and close... | Glassdoor

Interview Question

Software Engineering Intern Interview

Given a set of open and close parenthesis, make sure the

  string is valid, such that each open parenthesis has a matching close parenthesis in the correct place.

Interview Answer

2 Answers


Use a stack - push on an open bracket, pop on a close bracket, and if a pop fails (due to an empty stack) then the string is invalid.

int on Oct 7, 2013

import java.util.*;
public class validString {
    public static boolean isValid(String str) {
        Set set = new HashSet();
        Map map = new HashMap();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        str = str.replaceAll("\\s", "");
        Stack stack = new Stack();
        for (int i = 0; i < str.length(); i++) {
            if (set.contains(str.charAt(i))) {
            } else {
                if (stack.empty()) return false;
                char c = stack.pop();
                if (map.get(str.charAt(i)) != c) return false;

        return stack.empty();

Anonymous on Sep 12, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.