Answer multi-round grid and data-structure questions

You are given several independent interview-style coding questions. ## 1) Find first/last occurrence in sorted array (+ dynamic updates follow-ups) Given an integer array `nums` sorted in **non-decreasing** order and an integer `target`, return a 2-element array `[firstIndex, lastIndex]` where: - `firstIndex` is the smallest index `i` such that `nums[i] == target` - `lastIndex` is the largest index `j` such that `nums[j] == target` - if `target` does not appear, return `[-1, -1]` **Constraints (typical):** `0 <= n <= 2e5`, values fit in 32-bit signed int. **Follow-ups (discuss approach):** 1. If the array keeps receiving insertions only at the end, and every inserted number is **greater than the current last element** (so the array stays sorted), how would you update/answer range queries efficiently? 2. If insertions can happen **anywhere** (while keeping the overall order non-decreasing), how would you support both insertions and `[first,last]` range queries efficiently? --- ## 2) Implement an O(1) lottery participant store Design a data structure `LotterySystem` supporting the following operations with **expected O(1)** time: - `LotterySystem()` – initialize the structure - `boolean addParticipant(int id)` – add a participant with **unique** `id`; return `true` if added, `false` if already present - `boolean removeParticipant(int id)` – remove a participant by `id`; return `true` if removed, `false` if not present - `int randomPick()` – return a uniformly random participant id among current participants; return `-1` if empty --- ## 3) Extract the string(s) at maximum parenthesis depth Given a string `s` consisting of lowercase letters and parentheses `'('`, `')'`, assume parentheses are **balanced**. Define the **nesting depth** as the number of currently open parentheses. Return a string consisting of **all characters whose depth equals the maximum depth** anywhere in the string, in their original order. **Examples** - `s = "a(b(c)d)e"` → max depth is 2 → output `"c"` - `s = "((ab)(cd))"` → max depth is 2 → output `"abcd"` **Constraints (typical):** `|s| <= 2e5`. --- ## 4) Place one turret to protect the most houses (Manhattan radius) You are given an `m x n` 2D grid where each cell is either a house (`1`) or empty (`0`). You may place **one** turret on any cell. A turret protects a house if the Manhattan distance from the turret to that house is `<= k`: \[ |r_1-r_2| + |c_1-c_2| \le k \] Return the **maximum** number of houses that can be protected. **Constraints (typical):** `1 <= m,n <= 2000` (or discuss scalable approaches), `0 <= k <= 2000`. --- ## 5) Shortest path in grid with up to k wall breaks Given an `m x n` grid where: - `0` = empty cell - `1` = wall Starting at `(0,0)`, you want to reach `(m-1,n-1)` with 4-directional moves. You may traverse through at most `k` wall cells total (i.e., “break” up to `k` walls). Return the length of the shortest path (number of steps), or `-1` if impossible. **Constraints (typical):** `1 <= m,n <= 100`, `0 <= k <= m*n`.