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.