What is Interview Forge?

Interview Forge helps you practice mock interviews, follow study plans, track career goals, review learning analytics, and prepare across 36 pages.

Valid Parentheses at Meta — Interview Guide

The problem at Meta

Given a string containing only '(', ')', '{', '}', '[' and ']', determine whether the input is valid: every opening bracket must be closed by the same type, in the correct order, and every closing bracket must match the most recent unmatched opening bracket.

Meta uses this problem to assess move fast, ship impact, scale thinking. Expect Meta-specific follow-ups that tie the solution back to production reasoning and the company's engineering bar.

Key concepts

Last-in, first-out matching makes a stack the natural data structure.
A closing bracket must match the top of the stack; otherwise the string is invalid.
At the end, the stack must be empty (no unclosed openers).

Approach

Map each closing bracket to its opening bracket.
Push opening brackets onto a stack.
For a closing bracket, if the stack is empty or the top does not match, return false; otherwise pop.
Return true only if the stack is empty at the end.

def is_valid(s):
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pair.values():
            stack.append(c)
        elif c in pair:
            if not stack or stack[-1] != pair[c]:
                return False
            stack.pop()
    return not stack

Complexity

Metric	Value
Time	O(n)
Space	O(n)

Unlock the full guide

Premium members get every DSA, system design, company and role interview guide — plus AI practice, mock interviews, and analytics.

Unlock with Premium