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.