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.

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/

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.

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

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

Loading coding console...

Show the approach

Approach

We implement a dispatcher function. For 'closest_bst', we first reconstruct the tree from its level-order representation (children at 2i+1 and 2i+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