# The Gate Keeper

> Not all openings have a closing.

Canonical URL: <https://datadriven.io/problems/the_gate_keeper>

Domain: Python · Difficulty: easy · Seniority: L4

## Problem

Given a string of only '()[]{}' characters, return True if all brackets are properly matched and nested, else False.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **stack-based bracket matching** algorithm, one of the most classic data structure problems. It probes whether a candidate understands LIFO ordering and can map opening brackets to their closing counterparts.

---

### Break down the requirements

#### Step 1: Push opening brackets onto a stack

When you encounter `(`, `{`, or `[`, push it.

#### Step 2: Pop and match on closing brackets

When you encounter `)`, `}`, or `]`, pop the stack and verify the bracket types match.

#### Step 3: Check for empty stack at the end

If the stack is not empty, there are unmatched opening brackets.

---

### The solution

**Stack-based bracket matching**

```python
def is_valid(s: str) -> bool:
    stack = []
    matches = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in matches:
            if not stack:
                return False
            top = stack.pop()
            if top != matches[ch]:
                return False
        else:
            stack.append(ch)
    is_balanced = len(stack) == 0
    return is_balanced
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the string length. Each character is pushed and popped at most once.
> 
> **Space:** O(n) in the worst case (all opening brackets).

> **Interviewers Watch For**
>
> Whether you check for an empty stack before popping. A closing bracket with nothing on the stack is invalid.

> **Common Pitfall**
>
> Only checking parentheses and forgetting curly braces or square brackets. Use a mapping dict to handle all three types uniformly.

---

## Common follow-up questions

- What if the string contains non-bracket characters? _(Tests skipping characters not in the bracket set.)_
- How would you find the position of the first mismatch? _(Tests tracking indices alongside the stack.)_
- How would you add support for angle brackets? _(Tests extending the matches dict with `'>': '<'`.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_gate_keeper)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.