Implement solutions to several coding tasks

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.