How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at WeRide.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at WeRide during technical interviews.

Validate Bracket Sequence | WeRide Coding Question

Validate Bracket Sequence

Company: WeRide

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Given a string containing only the characters `()[]{}`, determine whether the brackets are properly matched. A bracket string is considered valid if: - Every opening bracket has a corresponding closing bracket of the same type. - Brackets close in the correct order. - Every closing bracket matches the most recent unmatched opening bracket. Return `true` if the string is valid, otherwise return `false`. Examples: - `"()[]{}"` -> `true` - `"([{}])"` -> `true` - `"(]"` -> `false` - `"([)]"` -> `false` - `"(("` -> `false` Discuss the expected time and space complexity of your approach.

Quick Answer: This question evaluates proficiency with stack data structures, string parsing and matching logic, and the ability to reason about algorithmic time and space complexity.

Given a string `s` containing only the characters `()[]{}`, determine whether the bracket sequence is valid. A bracket string is considered valid if: - Every opening bracket has a corresponding closing bracket of the same type. - Brackets close in the correct order. - Every closing bracket matches the most recent unmatched opening bracket. Return `True` if the string is valid, otherwise return `False`. Examples: - `"()[]{}"` -> `True` - `"([{}])"` -> `True` - `"(]"` -> `False` - `"([)]"` -> `False` - `"(("` -> `False`

Constraints

0 <= len(s) <= 100000
s consists only of the characters ()[]{}

Examples

Input: "()[]{}"

Expected Output: True

Explanation: Each opening bracket is matched by the correct closing bracket in a valid order.

Input: "([{}])"

Expected Output: True

Explanation: The brackets are properly nested, so every closing bracket matches the most recent opening bracket.

Input: "(]"

Expected Output: False

Explanation: The opening `(` is closed by `]`, which is the wrong type.

Input: "([)]"

Expected Output: False

Explanation: Although the counts match, the closing order is incorrect because `)` tries to close `(` before `[` is closed.

Input: "(("

Expected Output: False

Explanation: There are unmatched opening brackets remaining at the end.

Input: ""

Expected Output: True

Explanation: An empty string has no unmatched brackets, so it is valid.

Input: "]"

Expected Output: False

Explanation: A closing bracket appears before any matching opening bracket.

Hints

Try processing the string from left to right while keeping track of opening brackets that have not been matched yet.
A stack is useful when you need to match each closing bracket with the most recent unmatched opening bracket.

Quick Overview

This question evaluates proficiency with stack data structures, string parsing and matching logic, and the ability to reason about algorithmic time and space complexity.