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.

Longest Bounded-Difference Subarray

Return the length of the longest contiguous subarray whose maximum minus minimum is at most limit.

Examples

Example 1

Input: ([8,2,4,7], 4)
Output: 2

Explanation: The longest valid windows have length 2.

Example 2

Input: ([10,1,2,4,7,2], 5)
Output: 4

Explanation: The subarray [2,4,7,2] has max-min equal to 5.

Hints

1. Maintain decreasing and increasing deques for the current window.
2. Move the left edge until max-min is within the limit.

Dynamic Islands With Maximum Size

Starting from an all-water grid, add land cells one by one and return [islandCount, largestIslandSize] after each operation.

Examples

Example 1

Input: (3, 3, [[0,0],[0,1],[1,2],[2,1],[1,1]])
Output: [[1, 1], [1, 2], [2, 2], [3, 2], [1, 5]]

Explanation: The final add connects all existing islands into one size-5 island.

Example 2

Input: (2, 2, [[0,0],[1,1],[0,1]])
Output: [[1, 1], [2, 1], [1, 3]]

Explanation: The third add merges two diagonal components through a side neighbor.

Hints

1. Use union-find keyed only by land cells.
2. Track component sizes at roots so the maximum can be updated after each union.

Hit Counter Queries

Given hit timestamps and query timestamps, return how many hits occurred in the inclusive trailing window for each query.

Constraints

• hits and queries are integer timestamps.
• window is a positive number of seconds.
• Multiple hits at the same timestamp are counted separately.

Examples

Example 1

Input: ([1,2,3,300,301], [300,301,600], 300)
Output: [4, 4, 1]

Explanation: Each query counts hits in the inclusive trailing 300-second window.

Example 2

Input: ([], [10,20], 300)
Output: [0, 0]

Explanation: No hits means every query returns zero.

Hints

1. Sort the hits once.
2. Use binary search to count timestamps inside each query window.