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.