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 Technical Screen rounds at TikTok.

What role is this question designed for?

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

Solve three string/stack/backtracking problems

Quick Overview

This set evaluates proficiency with algorithmic patterns—stack-based and monotonic-stack reasoning for visibility problems, backtracking for combinatorial generation of balanced parentheses, and greedy/stack techniques for string validity—along with complexity analysis and handling large input constraints.

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given three independent coding tasks (solve each one). Unless otherwise stated, implement a function with the described input/output. ## Problem A (Monotonic stack) Given an array `heights` of length `n` where `heights[i]` is the height of the `i`-th person standing in a line (from left to right). For each person `i`, compute how many people to the **right** are **visible** to person `i`. A person `j > i` is visible to `i` if: - For every `k` with `i < k < j`, `heights[k] < min(heights[i], heights[j])`. Return an array `ans` of length `n` where `ans[i]` is the number of visible people to the right of `i`. **Constraints (typical):** `1 <= n <= 1e5`, `1 <= heights[i] <= 1e9`. ## Problem B (Backtracking) Given an integer `n`, generate **all** strings containing exactly `n` pairs of parentheses that are **balanced**. Return the list of valid strings in any order. **Constraints (typical):** `0 <= n <= 10`. ## Problem C (Greedy / Stack) Given a string `s` consisting of lowercase letters and parentheses `'('` and `')'`, remove the **minimum number** of parentheses so that the resulting string is a **valid parentheses string** (letters are always allowed and do not affect validity). Return **any** valid result after minimum removals. A parentheses string is valid if parentheses are balanced and properly nested. **Constraints (typical):** `1 <= |s| <= 1e5`.

Quick Answer: This set evaluates proficiency with algorithmic patterns—stack-based and monotonic-stack reasoning for visibility problems, backtracking for combinatorial generation of balanced parentheses, and greedy/stack techniques for string validity—along with complexity analysis and handling large input constraints.

Part 1: Monotonic Stack - Number of Visible People to the Right

You are given a list `heights` where `heights[i]` is the height of the `i`-th person standing in a line from left to right. For each person `i`, compute how many people to the right are visible to them. A person `j > i` is visible from `i` if every person between `i` and `j` has height strictly smaller than `min(heights[i], heights[j])`. Return a list `ans` where `ans[i]` is the number of visible people to the right of person `i`.

Constraints

1 <= len(heights) <= 100000
1 <= heights[i] <= 10^9

Examples

Input: [10, 6, 8, 5, 11, 9]

Expected Output: [3, 1, 2, 1, 1, 0]

Explanation: Person 0 can see 6, 8, and 11. The full visible counts are [3, 1, 2, 1, 1, 0].

Input: [5]

Expected Output: [0]

Explanation: Edge case: with only one person, nobody is to the right.

Input: [1, 2, 3, 4]

Expected Output: [1, 1, 1, 0]

Explanation: Each person can only see the next taller person immediately to their right.

Input: [5, 5, 5]

Expected Output: [1, 1, 0]

Explanation: Equal heights block further visibility after the first visible person.

Hints

Process people from right to left so the relevant information about the suffix is already available.
A decreasing stack helps remove shorter people that are directly visible, while the next remaining taller or equal person is also visible.

Part 2: Backtracking - Generate Balanced Parentheses

Given an integer `n`, generate all strings that contain exactly `n` pairs of parentheses and are balanced. A balanced string never has more closing parentheses than opening parentheses in any prefix, and the total numbers of `(` and `)` are equal. For deterministic output, return the list in lexicographic order.

Constraints

0 <= n <= 10

Examples

Input: 0

Expected Output: ['']

Explanation: Edge case: with zero pairs, the only valid string is the empty string.

Input: 1

Expected Output: ['()']

Explanation: There is only one balanced string with one pair.

Input: 2

Expected Output: ['(())', '()()']

Explanation: These are the two valid balanced strings for two pairs.

Input: 3

Expected Output: ['((()))', '(()())', '(())()', '()(())', '()()()']

Explanation: All five balanced combinations for three pairs are returned in lexicographic order.

Hints

Build the string one character at a time. Keep track of how many opening and closing parentheses you have used.
You can always add `(` if you still have some left, but you can only add `)` when it will not make the prefix invalid.

Part 3: Greedy / Stack - Minimum Removal to Make Parentheses Valid

You are given a string `s` containing lowercase English letters and parentheses `(` and `)`. Remove the minimum number of parentheses so that the resulting string is a valid parentheses string. Letters are always kept and do not affect validity. Return any valid result after minimum removals.

Constraints

1 <= len(s) <= 100000
`s` contains only lowercase English letters, `(`, and `)`

Examples

Input: 'lee(t(c)o)de)'

Expected Output: 'lee(t(c)o)de'

Explanation: The final `)` is unmatched, so removing it makes the string valid.

Input: 'a)b(c)d'

Expected Output: 'ab(c)d'

Explanation: The `)` after `a` is unmatched and must be removed.

Input: '))(('

Expected Output: ''

Explanation: Edge case: every parenthesis is unmatched, so the valid result is the empty string.

Input: 'abc'

Expected Output: 'abc'

Explanation: There are no parentheses to fix, so the string stays the same.

Input: '(()'

Expected Output: '()'

Explanation: One unmatched `(` must be removed.

Hints

A closing parenthesis without a matching earlier opening parenthesis must be removed immediately.
After one left-to-right pass, any unmatched opening parentheses left in the stack must also be removed.

Quick Overview