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 hard difficulty Coding & Algorithms question, commonly asked during HR Screen rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Backend Engineer candidates at Bytedance during technical interviews.

Solve Bracket Matching and Tree Width | Bytedance Coding Question

Quick Overview

This composite question evaluates proficiency with core data structures and algorithmic reasoning, covering string-based bracket validation (sequence matching and nesting correctness) and binary-tree level-span computation using position indexing and attention to numerical robustness.

Solve Bracket Matching and Tree Width

Company: Bytedance

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: HR Screen

Solve both coding problems below. ## Problem 1: Validate Balanced Brackets Given a string `s` containing only the characters `(`, `)`, `{`, `}`, `[` and `]`, determine whether the brackets are valid. A string is valid if: 1. Every opening bracket is closed by the same type of bracket. 2. Opening brackets are closed in the correct order. 3. Every closing bracket has a corresponding previous opening bracket. Return `true` if the string is valid; otherwise return `false`. ### Examples ```text Input: s = "()[]{}" Output: true ``` ```text Input: s = "([)]" Output: false ``` ```text Input: s = "{[]}" Output: true ``` ### Constraints - `0 <= s.length <= 100000` - `s` contains only bracket characters. --- ## Problem 2: Compute the Maximum Level Span in a Binary Tree You are given the root of a binary tree. For each depth level, imagine the tree is placed into a full binary tree layout where the root has position index `0`, a node at index `i` has left child index `2 * i` and right child index `2 * i + 1`. The span of a level is: ```text rightmost_position_index - leftmost_position_index + 1 ``` This span includes the gaps between existing nodes. Return the maximum span among all levels. ### Example ```text Input tree: 1 / \ 3 2 / \ 5 9 Position indexes by level: Level 0: 1 at index 0, span = 1 Level 1: 3 at index 0, 2 at index 1, span = 2 Level 2: 5 at index 0, 9 at index 3, span = 4 Output: 4 ``` ### Constraints - The number of nodes is between `0` and `100000`. - Node values are irrelevant. - Your solution should run in `O(n)` time, where `n` is the number of nodes. - Be careful to avoid integer overflow when assigning position indexes.

Quick Answer: This composite question evaluates proficiency with core data structures and algorithmic reasoning, covering string-based bracket validation (sequence matching and nesting correctness) and binary-tree level-span computation using position indexing and attention to numerical robustness.

Part 1: Validate Balanced Brackets

Given a string s containing only bracket characters '(', ')', '{', '}', '[' and ']', determine whether the brackets are balanced and properly nested. A valid string must close every opening bracket with the same bracket type, close brackets in the correct order, and never contain a closing bracket without a matching previous opening bracket.

Constraints

0 <= len(s) <= 100000
s contains only the characters '(', ')', '{', '}', '[' and ']'.

Examples

Input: ""

Expected Output: True

Explanation: The empty string contains no unmatched brackets, so it is valid.

Input: "()[]{}"

Expected Output: True

Explanation: Each bracket is closed by the same type in the correct order.

Input: "([)]"

Expected Output: False

Explanation: The '[' bracket is opened after '(' but ')' tries to close '(' first, so the nesting order is invalid.

Input: "{[]}"

Expected Output: True

Explanation: The brackets are correctly nested.

Input: "((()"

Expected Output: False

Explanation: There are unmatched opening parentheses remaining.

Hints

When you see an opening bracket, remember it until its matching closing bracket appears.
The most recently opened bracket must be the first one closed.

Part 2: Compute the Maximum Level Span in a Binary Tree

You are given the shape of a binary tree. Nodes are indexed from 0 to n - 1, and node 0 is the root when the tree is non-empty. For each depth level, imagine the tree placed into a full binary tree layout where the root has position index 0, a node at position i has left child position 2 * i, and right child position 2 * i + 1. The span of a level is rightmost_position_index - leftmost_position_index + 1, including gaps between existing nodes. Return the maximum span over all levels.

Constraints

0 <= len(children) <= 100000
If len(children) > 0, node 0 is the root.
Each children[i] has exactly two integers: [left_child_index, right_child_index].
Each child index is either -1 or an integer in the range [0, len(children) - 1].
The input represents a valid binary tree: no cycles, no node has more than one parent, and all nodes are reachable from the root when non-empty.
The solution should run in O(n) time.
Avoid relying on unbounded raw position indexes growing with tree depth; normalize positions by level.

Examples

Input: []

Expected Output: 0

Explanation: The tree is empty, so there are no levels.

Input: [[-1, -1]]

Expected Output: 1

Explanation: A single-node tree has span 1 at its only level.

Input: [[1, 2], [3, -1], [-1, 4], [-1, -1], [-1, -1]]

Expected Output: 4

Explanation: At level 2, node 3 is at position 0 and node 4 is at position 3, giving span 3 - 0 + 1 = 4.

Input: [[1, -1], [2, -1], [3, -1], [-1, -1]]

Expected Output: 1

Explanation: The tree is a single left chain, so every level contains exactly one node.

Input: [[1, 2], [3, -1], [-1, 4], [5, -1], [-1, 6], [-1, -1], [-1, -1]]

Expected Output: 8

Explanation: At level 3, the leftmost node is at position 0 and the rightmost node is at position 7, so the span is 8.

Hints

Use breadth-first search so you can process one level at a time.
At each level, subtract the first node's position from all positions before generating child positions to keep numbers small.

Quick Overview