Solve four algorithmic problems
Overview
This multi-part question evaluates algorithmic problem-solving and data-structure proficiency across string processing (validating parentheses with minimal deletions), tree operations (lowest common ancestor using parent pointers), nested-structure traversal and accumulation (depth-weighted sum), and geometric selection/ordering (k closest points).
Solve the following coding tasks. For each, describe your approach, complexity, and handle edge cases.
1) Make parentheses string valid with minimal deletions
Input: a string s containing lowercase letters and parentheses '(', ')'.
Task: Remove the minimum number of characters so the resulting string has valid parentheses (every closing parenthesis matches a previous unmatched opening parenthesis, and parentheses are properly nested). Return any valid result.
Constraints (typical): 1 <= len(s) <= 1e5.
2) Lowest common ancestor with parent pointers
You are given two nodes p and q in a tree where each node has a pointer to its parent (and optionally left/right if it’s a binary tree).
Task: Return their lowest common ancestor (the deepest node that is an ancestor of both). You may assume both nodes belong to the same tree.
Constraints (typical): up to 1e5 nodes.
3) Weighted sum of a nested integer list
Input: a nested list structure where each element is either an integer or a nested list (arbitrary depth).
Task: Compute the depth-weighted sum: each integer is multiplied by its depth (top-level depth = 1).
Example: [1,[4,[6]]] → 1*1 + 4*2 + 6*3 = 27.
4) K closest points to the origin
Input: an array of points points[i] = (xi, yi) and an integer k.
Task: Return any k points with the smallest Euclidean distance to the origin (distance comparison can use squared distance xi^2 + yi^2).
Constraints (typical): 1 <= n <= 1e5.
Note: If distances tie, any order is acceptable unless specified otherwise.