The Gate Keeper

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
L4

Problem

An expression validator receives short strings built only from the bracket characters ()[]{} and has to confirm each one is well-formed before it moves downstream. A string is valid when every opening bracket is closed by one of the same type in the correct order with nothing left open, so ([)] fails even though the counts balance; an empty string counts as valid.

Not all openings have a closing.

Example 1

Input:

s = "()[]{}"

Output:

true

Example 2

Input:

s = "([)]"

Output:

false

Worked solution and explanation

What this really is under the costume

This is the classic balanced-brackets check wearing a validator's clothes. The skill being probed: do you reach for a last-in-first-out structure to remember the most recent bracket you still owe a close to? Anyone can balance a flat run of one bracket type with a counter. Nesting is what breaks the counter, because a close has to match the MOST RECENT open, not just any open. The whole problem lives in two empty-stack edges, and candidates lose it on exactly those.

Step 1: On an opener, remember it

Push the character. The stack now remembers it as the innermost bracket still waiting to be closed.

Step 2: On a closer, settle the most recent opener

Pop the stack and check the popped opener is the partner of this closer. If they disagree, the nesting is crossed (this is what kills ([)]) and you can bail immediately. If the stack was already empty, you are closing something that was never opened, so bail too.

Step 3: Demand an empty stack at the end

After the last character, a non-empty stack means openers were never closed. Only an empty stack is valid, which is also why the empty string is valid: nothing was ever left owing.

Stack-based bracket matching
def is_valid_parens(s):
    stack = []
    partner = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in partner:
            if not stack or stack.pop() != partner[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

One pass, pop-and-compare on every closer, empty-stack check at the end.

Common follow-up questions