Open and Shut

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L5
Asked in
Walmart

Problem

A config parser has to reject malformed input before it reaches the evaluator. Given a string s that mixes the three bracket pairs (), [], {} with arbitrary other characters, return whether every bracket is closed by the correct type and in the right nesting order. Treat any non-bracket character as filler, and treat an empty string as balanced.

Every opener is a promise. The order you close them in decides whether it holds.

Example 1

Input:

s = "({[]})"

Output:

true

Example 2

Input:

s = "([)]"

Output:

false

Worked solution and explanation

What this really is

Strip the validator framing and this is a last-in-first-out matching problem: the most recently opened bracket must be the next one to close. Anyone can count brackets and confirm the totals line up. What actually separates candidates is catching the two strings where counting lies. In '([)]' the counts are perfect but the square bracket closes while a parenthesis is still open, so the nesting is wrong. In '({' nothing ever mismatches, yet two openers are left dangling at the end. Miss either and your validator waves malformed input straight through to the evaluator.

Break down the requirements

Step 1: Map closing brackets to their openers

Build a dict mapping each closer to its opener: ) to (, ] to [, } to {. One lookup replaces a chain of if/elif comparisons and makes the match check a single expression.

Step 2: Push openers, pop and match closers

Walk the string once. An opener gets pushed. A closer must find a matching opener on top of the stack, else you can bail immediately. Anything that is neither is filler and gets skipped, which is what makes 'hello (world)' work without special-casing letters.

Step 3: Verify the stack is empty at the end

The loop alone is not enough. A string like '({' never triggers a mismatch because no closer ever arrives. The only way to catch leftover openers is to confirm the stack is empty once the loop ends.

The solution

Stack-based bracket matching with pair validation
def is_balanced(s):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in matching:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
    return not stack

One pass, O(n) time; the closing check covers both the wrong-type and the empty-stack cases.

Common follow-up questions