The "Valid Parentheses" interview question is one of the most famous problems in coding history. You are given a string containing just the characters (, ), {, }, [ and ]. You must determine if the input string is valid. A string is valid if open brackets are closed by the same type of brackets, and brackets are closed in the correct order.
This "Valid Parentheses" coding problem is used by almost every major tech company, including Apple, Google, and Microsoft. It is the definitive way to test if a candidate understands the "Stack interview pattern." It mimics real-world scenarios like compiler parsing, HTML tag validation, and expression evaluation.
The core algorithmic pattern is the "Stack." As you iterate through the string, you push every opening bracket onto a stack. When you encounter a closing bracket, you check if the stack is empty or if the top of the stack matches the corresponding opening bracket. If it matches, you pop it; otherwise, the string is invalid. Finally, the stack must be empty for the string to be valid.
Let's trace the string "{[]}".
{: Push to stack. Stack: ['{'].[: Push to stack. Stack: ['{', '['].]: Closing bracket. Top of stack is [. Match! Pop it. Stack: ['{'].}: Closing bracket. Top of stack is {. Match! Pop it. Stack: [].One frequent mistake is forgetting to check if the stack is empty before popping when a closing bracket is encountered (this happens with strings like ")"). Another is not checking if the stack is empty at the very end (this happens with strings like "(()"). Some candidates also try to use counters instead of a stack, which fails for cases like "([)]" where the count is correct but the order is wrong.
Use a hash map (dictionary) to store the pairs of brackets (e.g., ')': '('). This makes your code much cleaner and easier to extend if more types of brackets are added. Instead of multiple if-else blocks, you can simply check if the current character is a key in your map.