Implement three interview-style coding tasks

You are given three separate coding tasks, all focused on algorithm and data-structure design. --- ### Task 1: Longest Bounded-Difference Subarray You are given an integer array `nums` and an integer `limit`. Find the length of the longest **contiguous** subarray such that the absolute difference between the maximum and minimum elements in that subarray is **less than or equal to** `limit`. - **Input:** - `nums`: an array of integers, length `n` (e.g., `1 <= n <= 10^5`). - `limit`: an integer. - **Output:** - An integer representing the maximum possible length of a contiguous subarray `[i..j]` such that `max(nums[i..j]) - min(nums[i..j]) <= limit`. - **Example (for illustration):** - `nums = [8, 2, 4, 7], limit = 4` → answer = `2` (subarray `[2,4]`). Design an algorithm that runs in (amortized) linear time with respect to `n`. --- ### Task 2: Dynamic Islands Count With Max Island Size You are given a 2D grid of size `m x n`, initially filled with water (`0`). You receive a sequence of operations; each operation turns a water cell into land (`1`). Land cells are connected **4-directionally** (up, down, left, right). For each operation, you must maintain **both**: 1. The current number of islands (connected components of land), and 2. The size (number of cells) of the **largest island** after that operation. - **Input:** - Two integers `m`, `n` specifying grid dimensions (`m, n` can be up to, say, `10^4` each; total cells `m * n` can be large). - A list `positions` of length `k` where each element is a pair `[r, c]` indicating that the cell at row `r`, column `c` (0-indexed) is converted from water to land in that step. - You may assume no position is added more than once. - **Output:** - For each operation `i` (0-based), output two numbers: - `islandCount[i]`: the number of islands after operation `i`. - `maxIslandSize[i]`: the size of the largest island after operation `i`. You should design a data structure and algorithm that can process all `k` operations efficiently (much faster than recomputing all islands from scratch after each operation). --- ### Task 3: Hit Counter and Simple Rate Limiter You are asked to design two related components. #### 3a. Hit Counter for Last 5 Minutes Design an in-memory hit counter with the following API: - `hit(timestamp)`: Record a hit at time `timestamp` (in seconds). - `getHits(timestamp)`: Return the number of hits received in the **past 300 seconds** (5 minutes), including at `timestamp`. Assume: - `timestamp` is a positive integer representing seconds. - Calls to `hit` and `getHits` use **non-decreasing** timestamps (i.e., new timestamps are never in the past). Design the data structures and algorithms so that both operations are efficient in time and memory, even when the number of hits is large. #### 3b. Extend to a Per-User Request Rate Limiter Now extend your design to implement a simple **per-user rate limiter**. Provide an API like: - `shouldAllow(userId, timestamp) -> bool` This should: - Return `true` if the given `userId` has made **fewer than `N` requests** in the last `W` seconds (including the current one), and the new request should be allowed. - Return `false` if allowing this request would exceed the configured rate limit of `N` requests per rolling window of `W` seconds. You may assume: - `N` and `W` are given configuration parameters (for example, `N = 100`, `W = 60` seconds). - `timestamp` is again in seconds and **non-decreasing** per process. Specify: - What data structures you would use. - How you would update and clean up data as time moves forward. - The expected time and space complexity per call.