Valid Parentheses Interview Question

Practice Java Interview Questions

Question:

“This question is to test your ability to know what data structure to use as that is supremely important. For this question we want to understand your thought process so give a thorough explanation. We want to make sure a certain user’s response to a question has valid parentheses and quotations, so the character set would include [], (), ‘’, “”, and {}. By valid we mean that every opening character has a corresponding closing character, THE OPPOSITE DOES NOT HAVE TO BE TRUE. We want to make sure that an opening character has the corresponding closing character. Can you tell us which data structure would be your main one to accomplish this? And can you provide us the completed code from the one provided here:”

class ValidParentheses {
   public boolean isValid(String s) {
      //code goes here
   }
}

Answer:

“Since the logic would be to traverse a string in sequential order and keep track of each special opening character(special character meaning the characters we’re looking for) and as we keep track we make sure that if the current special character is a closing type then the last special opening character we have been keeping track of is the same opening type. I would use a stack data structure to keep track of the special characters and if we come across a closing type we check if the top of the stack is the same opening type. Then we pop that opening type from the stack and continue. If we find a condition that violates this then the string does not have valid parentheses.”

//Main.java
import java.util.HashMap;
import java.util.Stack;
class Main {
   public static boolean isValid(String s) {
      Stack<Character> stack = new Stack<>();
      HashMap<Character, Character> special = new HashMap<>();
      special.put('\'', '\'');
      special.put('"', '"');
      special.put('(', ')');
      special.put('[', ']');
      special.put('{', '}');
      for(int i = 0; i < s.length(); i++){
         char c  =  s.charAt(i);
         if(!Character.isLetter(c)){
            if(special.containsKey(c)){
               if(!stack.isEmpty() && special.get(stack.peek()) != c)
                  stack.add(c);
               else if(stack.isEmpty())
                  stack.add(c);
               else
                  stack.pop();
            }
            else if(c == '\'' || c == '"' || c == ')' || c == '}'|| c == ']'){
               if(!stack.isEmpty() && special.get(stack.peek()) == c)
                  stack.pop();
               else if(stack.isEmpty())
                  return true;
               else
                  return false;
            }
         }
      }
      return stack.isEmpty();
   }
   public static void main(String[] args) {
      System.out.println(isValid("('Hello'))"));
   }
}

Additional Resources:

• https://www.javatpoint.com/java-stack
• https://www.educative.io/edpresso/the-valid-parentheses-problem