Microsoft OA Interview Question: Valid Parentheses | Coding Interview Stack Problem

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

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Examples:

Valid input

()
()[]{}
{()}

Invalid input

(]
()[]{({)}

This problem asks whether a bracket string is well-formed. The standard solution uses a stack: push every opening bracket, and when a closing bracket appears, check whether it matches the stack top. If the stack is empty or the types do not match, the string is invalid. After processing all characters, the stack must be empty for the string to be valid. It is a classic stack-matching question that tests correct handling of nesting and ordering.