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
Solution
from typing import Optional
class TreeNode:
__slots__ = ("val", "left", "right")
def __init__(self, val: int, left: Optional['TreeNode']=None, right: Optional['TreeNode']=None):
self.val = val
self.left = left
self.right = right
def _build_tree(level):
if not level:
return None
nodes = [None if v is None else TreeNode(int(v)) for v in level]
if nodes[0] is None:
return None
n = len(nodes)
for i in range(n):
node = nodes[i]
if node is None:
continue
li = 2 * i + 1
ri = 2 * i + 2
if li < n:
node.left = nodes[li]
if ri < n:
node.right = nodes[ri]
return nodes[0]
def _closest_bst_value(root: TreeNode, target: float) -> int:
best = root.val
node = root
while node is not None:
v = node.val
dv = abs(v - target)
db = abs(best - target)
if dv < db or (dv == db and v < best):
best = v
if target < v:
node = node.left
else:
node = node.right
return best
def _min_remove_no_stack(s: str) -> str:
# First pass: remove invalid closing parentheses
first = []
bal = 0
for ch in s:
if ch == '(':
bal += 1
first.append(ch)
elif ch == ')':
if bal == 0:
continue
bal -= 1
first.append(ch)
else:
first.append(ch)
# Second pass: remove leftover opening parentheses from right
res = []
to_remove = bal
for ch in reversed(first):
if ch == '(' and to_remove > 0:
to_remove -= 1
continue
res.append(ch)
res.reverse()
return ''.join(res)
def solve_task(task: dict) -> object:
t = task.get('type')
if t == 'closest_bst':
tree = task.get('tree', [])
target = float(task.get('target', 0.0))
root = _build_tree(tree)
if root is None:
raise ValueError('Invalid tree: root is None')
return _closest_bst_value(root, target)
elif t == 'min_remove':
s = str(task.get('s', ''))
return _min_remove_no_stack(s)
else:
raise ValueError('Unknown task type')
Explanation
We implement a dispatcher function. For 'closest_bst', we first reconstruct the tree from its level-order representation (children at 2*i+1 and 2*i+2; None for missing nodes). Then we traverse the BST from root toward the target: at each node, update the best seen value by absolute difference, preferring the smaller value on ties, and move left or right according to the BST property. For 'min_remove', we avoid a stack by using two linear passes: (1) left-to-right to skip any ')' that would make the prefix invalid (track an open-parentheses counter), (2) right-to-left to remove exactly the surplus '(' left unmatched after the first pass. This yields a valid parentheses string with the minimum removals while preserving the order of other characters.
Time complexity: closest_bst: O(n) to build + O(h) search (h is tree height); min_remove: O(m) (m = len(s)). Space complexity: closest_bst: O(n) for nodes; min_remove: O(m) for output buffers.
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).