Solve common array/string/linked-list tasks

You may be asked one or more of the following independent coding tasks. For each task, implement an efficient algorithm and clearly state time/space complexity. ## 1) Weighted random index (O(1) extra space) Design a class that supports: - `init(weights)`: `weights[i]` is a positive integer weight for index `i`. - `pickIndex() -> int`: returns an index `i` with probability `weights[i] / sum(weights)`. **Constraints/notes** - Aim for fast sampling per call. - **Follow-up:** achieve **O(1) extra space** (mutating the input array is allowed). ## 2) Evaluate an arithmetic expression (O(1) extra space) Given a string `s` representing a valid expression containing non-negative integers, optional spaces, and operators `+`, `-`, `*`, `/` (integer division truncating toward zero), evaluate and return the result. **Constraints/notes** - No parentheses. - Use **O(1) extra space** beyond the input string. ## 3) Find first and last position in sorted array Given a sorted integer array `nums` (non-decreasing) and an integer `target`, return a pair `[left, right]` where: - `left` is the first index with value `target`, - `right` is the last index with value `target`, - return `[-1, -1]` if `target` does not exist. Target complexity: `O(log n)`. ## 4) Longest valid parentheses substring Given a string `s` consisting only of `'('` and `')'`, return the length of the longest contiguous substring that forms a valid parentheses sequence. ## 5) Partition a linked list around a value Given the head of a singly linked list and an integer `x`, reorder the list so that all nodes with values `< x` come before nodes with values `>= x`, preserving the original relative order within each partition. Return the new head. ## 6) Count palindromic substrings Given a string `s`, return the number of substrings of `s` that are palindromes. A substring is a contiguous segment of the string.