You are given several independent coding interview tasks. Solve each with the required time/space complexity. ## Problem 1: Find the minimum in a rotated sorted array You are given an array `nums` of **distinct** integers that was originally sorted in increasing order and then rotated at an unknown pivot (e.g., `[4,5,6,7,0,1,2]`). - **Input:** `nums: int[]` - **Output:** the minimum value in `nums` - **Constraints:** `1 ≤ len(nums) ≤ 2e5` - **Expected complexity:** `O(log n)` time, `O(1)` extra space ## Problem 2: Time-based key-value store (variation) Design a data structure that supports storing and querying values for a key over time. Support the following operations: - `set(key: string, value: string, timestamp: int) -> void` - Stores the value for `key` at the given timestamp. - `get(key: string, timestamp: int) -> string` - Returns the value associated with `key` at the **largest timestamp ≤ query timestamp**. - If there is no such timestamp for the key, return an empty string. Assumptions/constraints: - Timestamps are integers. - For the same key, `set()` calls may arrive in increasing timestamp order (state your assumption); handle the general case if not. - Target: near `O(log m)` per `get()` for `m` versions of a key. ## Problem 3: Lowest common ancestor in a binary tree Given the root of a binary tree and two nodes `p` and `q` that both exist in the tree, return their **lowest common ancestor (LCA)**. - The LCA of `p` and `q` is the lowest node in the tree that has both `p` and `q` as descendants (a node can be a descendant of itself). ## Problem 4: Mark a path on a maze You are given: - A 2D maze grid `maze` represented as a list of equal-length strings. - `'#'` = wall - `'.'` = open cell - `'e'` = entrance (must stay as `'e'`) - `'E'` = exit (must stay as `'E'`) - A list `path` of coordinates (row, col) representing a valid path through the maze **including the entrance and exit**. Write a function that returns a new maze where every coordinate in `path` is replaced with `'*'`, **except** the entrance `'e'` and exit `'E'`, which must not be changed. - **Input:** `maze: string[]`, `path: (int row, int col)[]` - **Output:** `string[]` (the updated maze) - You may assume `path` contains only in-bounds coordinates and forms a valid path through open cells.