Closing Time

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
junior
Asked in
Cisco

Problem

Our query layer gates filter expressions before the parser sees them: each expression groups conditions with round, square, and curly brackets, and the gate confirms every opener is closed by the matching kind in the right order. Bracket characters inside a single-quoted string value are literal data, so they are ignored along with all other non-bracket characters. Return whether the brackets are balanced; an expression with no brackets is balanced.

Every bracket you open is a promise. Check that the parser keeps all of them.

Example 1

Input:

expr = "where(id in [10, 20], label = 'x(y')"

Output:

true

Example 2

Input:

expr = "a[b(c]d)"

Output:

false

Worked solution and explanation

Why this problem exists in real interviews

Strip the query-gate costume and this is a per-character LIFO match: the last bracket you opened must be the first one you close, and closed by the same kind. Most people who have not internalized that reach for counting, tallying opens against closes per type. It passes for ([]) and fails silently for ([)], where the counts balance perfectly but the nesting is garbage. The twist that punishes a memorized answer: a bracket sitting inside a quoted value like 'a(b]' is data the user typed, not structure, so a solution that matches every bracket it sees both green-lights nonsense and rejects valid input.

Why counting is not enough

Counting (broken)
Keep a tally per type and require each to end at zero. On a[b(c]d) you count one of each opener and one of each closer, the tallies zero out, and you wrongly return True. Counting throws away the one thing that matters: the ORDER unclosed brackets are waiting in.
Stack (correct)
Push every opener. On each closer, the only valid match is whatever is on top of the stack. For a[b(c]d the ] arrives while ( is on top, the kinds disagree, and you reject immediately. The stack remembers order, so interleaving cannot sneak through.

Break down the requirements

Step 1: Map each closer to its opener

A dict {')':'(', ']':'[', '}':'{'} turns the three bracket pairs into a single lookup. This also gives you two cheap membership tests: a character is an opener if it is one of the dict values, a closer if it is one of the dict keys.

Step 2: Track whether you are inside a quoted value

A single quote flips an in-string flag. While that flag is set, skip every character, brackets included, because those characters are text the user typed rather than structure. This flag is exactly what a recalled bracket matcher lacks: it has no notion that 'x(y' is data, so it tries to match the ( and corrupts the answer.

Step 3: Ignore everything that is not a bracket

Outside of quotes the expression still carries identifiers, commas, and operators. Walk character by character and simply skip anything that is neither an opener nor a closer. The non-bracket noise is irrelevant, but the bracket ORDER is not, which is why a counting hack feels tempting and is still wrong.

Step 4: Push openers, match closers against the top

On an opener, push it. On a closer, the stack must be non-empty AND its top must be the matching opener; otherwise return False right away. A closer with an empty stack means something closed that was never opened.

Step 5: Demand an empty stack at the end

Reaching the end is not success on its own. A leftover opener like count(items[0] means a promise never kept, so the answer is balanced only when the stack is empty. An input with no brackets at all leaves the stack empty and correctly returns True.

The solution

Single pass with a stack
def brackets_balanced(expr):
    pairs = {')': '(', ']': '[', '}': '{'}
    openers = set(pairs.values())
    stack = []
    in_string = False
    for ch in expr:
        if ch == "'":
            in_string = not in_string
        elif in_string:
            continue
        elif ch in openers:
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

Common follow-up questions