Solve four algorithmic problems

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.