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 Onsite rounds at Meta.

What role is this question designed for?

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

Find closest BST value and remove parentheses

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question LeetCode 270. Closest Binary Search Tree Value LeetCode 1249. Minimum Remove to Make Valid Parentheses (follow-up: achieve without using a stack) https://leetcode.com/problems/closest-binary-search-tree-value/description/ https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/

Quick Answer: This question evaluates understanding of binary search tree properties and numerical proximity reasoning alongside string parsing and parentheses validation, focusing on data structure manipulation and algorithmic reasoning.

Implement a single function solve_task(task) that performs one of two operations based on task['type']: 1) type = 'closest_bst': Given a Binary Search Tree encoded as a level-order array 'tree' (list of integers or None) and a numeric 'target' (float or int), return the BST node value (int) that is closest to target. If two values are equally close, return the smaller value. The array uses 0-based indexing; for index i, children are at 2*i+1 and 2*i+2; None denotes a missing child. The input is guaranteed to encode a valid BST and the root is not None. 2) type = 'min_remove': Given a string s, remove the minimum number of parentheses to make the string valid, preserving the relative order of the remaining characters. Non-parenthesis characters must remain in order and are not removed unless necessary for minimality. A valid string has balanced parentheses in correct order. Return an integer for 'closest_bst' and a string for 'min_remove'.

Constraints

For 'closest_bst': 1 <= number of nodes <= 100000
Node values are integers in [-1e9, 1e9]
target is a float or int in [-1e9, 1e9]
tree is a level-order array with None for missing nodes; root is not None; tree encodes a valid BST
For 'min_remove': 0 <= len(s) <= 100000
s contains ASCII characters; only '(' and ')' affect validity; other characters are preserved
Tie-breaking for 'closest_bst': if two values are equally close to target, return the smaller value
Follow-up: achieve 'min_remove' without using an explicit stack (two-pass approach is possible)

Examples

Input:

Expected Output: ab(c)d

Hints

For 'closest_bst', traverse from root using BST property, tracking the best value seen so far.
Update the best when you find a closer value; on a tie, prefer the smaller value.
For 'min_remove', use two passes: left-to-right to skip invalid ')', then right-to-left to skip leftover '('.
Avoid extra data structures for 'min_remove'; a counter and string builders suffice.
Build the tree from the level-order array using index relationships (2*i+1 and 2*i+2).

Quick Overview

This question evaluates understanding of binary search tree properties and numerical proximity reasoning alongside string parsing and parentheses validation, focusing on data structure manipulation and algorithmic reasoning.