Implement rate limiter, top-K, scheduler algorithms

Question

Design and implement a thread-safe Rate Limiter; extend it to support multi-threading and a version where current time is not passed as an argument. Implement binary search from scratch without using any library functions. Design a data structure/method getTopK that returns the top-K elements, using a doubly-linked-list–based approach. Design a Meeting Scheduler that finds available meeting slots across calendars; follow-ups include: applying MapReduce to scheduling, and ranking rooms with priority factors such as room-usage count and meeting duration.

Part 1: Sliding Window Rate Limiter

You are implementing the core decision logic of a thread-safe rate limiter. For a single shared client, process requests in timestamp order and decide whether each request is allowed. A request is allowed if fewer than limit accepted requests exist in the sliding window (t - window_size, t]. Denied requests do not count toward future windows.

Constraints

• 0 <= len(request_times) <= 200000
• 1 <= window_size <= 10^9
• 1 <= limit <= 10^5
• request_times is sorted in non-decreasing order

Examples

Example 1

Input: (3, 10, [1, 2, 3, 4, 14])
Output: [True, True, True, False, True]

Explanation: The fourth request arrives while three accepted requests are still inside the last 10 seconds. By time 14, the old accepted requests have expired.

Example 2

Input: (1, 10, [5, 5])
Output: [True, False]

Explanation: Only one request is allowed in the window, so the second request at the same time is denied.

Hints

1. Only accepted requests inside the current time window matter.
2. A queue or deque is enough because timestamps arrive in sorted order.

Part 2: Shared Rate Limiter Across Multiple Threads

Several threads share one global rate limiter. Each thread has its own non-decreasing list of request timestamps. Simulate the correct atomic behavior of a thread-safe limiter by processing all requests in ascending timestamp order. If two requests have the same timestamp, process the smaller thread index first, and within the same thread keep original order. Use the same sliding-window rule as Part 1: a request is allowed if fewer than limit accepted requests exist in (t - window_size, t].

Constraints

• 0 <= total number of requests across all threads <= 200000
• 1 <= number of threads <= 10000
• 1 <= window_size <= 10^9
• 1 <= limit <= 10^5
• Each thread's request list is sorted in non-decreasing order

Examples

Example 1

Input: (2, 5, [[1, 6], [1, 2], [7]])
Output: [[True, True], [True, False], [True]]

Explanation: The requests at time 1 from threads 0 and 1 are both allowed. The request at time 2 is denied because the limiter is already full.

Example 2

Input: (1, 3, [[], [1, 1], [4]])
Output: [[], [True, False], [True]]

Explanation: Edge case: one thread has no requests.

Hints

1. This is like merging k sorted lists while maintaining one shared sliding window.
2. A min-heap can give you the next global request in timestamp order.

Part 3: Rate Limiter With Internal Clock

Implement a rate limiter whose allow() method does not receive the current time as an argument. Instead, the limiter stores an internal clock. The clock starts at 0. You are given a sequence of operations: ('advance', x) means move the internal clock forward by x seconds, and ('allow',) means attempt one request at the current internal time. A request is allowed if fewer than limit accepted requests exist in (current_time - window_size, current_time].

Constraints

• 0 <= len(operations) <= 200000
• 1 <= window_size <= 10^9
• 1 <= limit <= 10^5
• Advance values are non-negative integers

Examples

Example 1

Input: (2, 5, [('allow',), ('allow',), ('allow',), ('advance', 5), ('allow',)])
Output: [True, True, False, True]

Explanation: Three immediate requests hit the limit; after advancing 5 seconds, the earlier accepted requests expire.

Example 2

Input: (1, 10, [('advance', 3), ('advance', 2)])
Output: []

Explanation: Edge case: no allow operations.

Hints

1. Treat allow as reading from stored state, not from a parameter.
2. Only accepted request times need to be stored.

Part 4: Binary Search for First Occurrence

Given a sorted array of integers and a target value, implement binary search from scratch without using any library search helpers. Return the index of the first occurrence of the target. If the target does not exist, return -1.

Constraints

• 0 <= len(nums) <= 200000
• nums is sorted in non-decreasing order
• -10^9 <= nums[i], target <= 10^9

Examples

Example 1

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

Explanation: The first 2 appears at index 1.

Example 2

Input: ([1, 3, 5, 7], 4)
Output: -1

Explanation: The target is not present.

Hints

1. When you find the target, do not stop immediately if duplicates may exist.
2. Think about how to shrink the search space toward the leftmost valid index.

Part 5: Top-K Frequent Elements with a Doubly Linked List

You receive a stream of integers. Each time a value appears, its frequency increases by 1. Implement getTopK using a doubly linked list of frequency buckets: each bucket stores all values with the same count, and buckets are ordered by frequency. After processing the full stream, return the top k most frequent values. Break ties by smaller numeric value first.

Constraints

• 0 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= number of distinct values or larger

Examples

Example 1

Input: ([5, 2, 5, 3, 2, 5, 2, 4], 2)
Output: [2, 5]

Explanation: Values 2 and 5 both have frequency 3, so the smaller value comes first.

Example 2

Input: ([], 3)
Output: []

Explanation: Edge case: empty stream.

Hints

1. Move an element only from frequency f to frequency f + 1 as you process the stream.
2. A map from value to its current bucket lets you update frequencies in O(1) amortized time.

Part 6: Common Free Slots Across Calendars

Given multiple people's calendars and working bounds, find all meeting slots that are free for everyone and have length at least duration. Each busy interval is half-open [start, end), so a meeting ending at time t does not conflict with one starting at t. Calendars may be unsorted and may contain overlapping busy intervals.

Constraints

• 1 <= number of people <= 200
• 0 <= total number of busy intervals <= 200000
• 0 <= start < end <= 1440
• Each bounds entry satisfies 0 <= work_start < work_end <= 1440

Examples

Example 1

Input: ([[[540, 570], [630, 660]], [[585, 600]], [[600, 615]]], [[540, 720], [540, 720], [540, 720]], 15)
Output: [[570, 585], [615, 630], [660, 720]]

Explanation: These are the gaps that remain after merging all busy intervals inside the shared workday.

Example 2

Input: ([[[60, 120], [90, 150]], []], [[0, 200], [50, 180]], 20)
Output: [[150, 180]]

Explanation: The overlapping intervals on the first calendar merge into one busy block [60, 150).

Hints

1. First reduce the search space to the intersection of all working bounds.
2. Merge overlapping or touching busy intervals before looking for gaps.

Part 7: MapReduce-Style Meeting Scheduler

Busy intervals are distributed across multiple shards. Each shard contains the busy intervals of some subset of employees, all within the same global workday. Emulate a MapReduce-style solution: the map phase emits interval boundary events, and the reduce phase combines those events to find all free time ranges where nobody is busy. Return the free slots of length at least duration inside [day_start, day_end).

Constraints

• 0 <= number of shards <= 10000
• 0 <= total busy intervals across all shards <= 200000
• 0 <= day_start < day_end <= 10^9
• Intervals may be unsorted, overlapping, or partially outside the day bounds

Examples

Example 1

Input: ([[[540, 600], [660, 690]], [[555, 570], [630, 660]], [[600, 630], [690, 720]]], 540, 780, 30)
Output: [[720, 780]]

Explanation: All busy blocks connect into one large interval [540, 720).

Example 2

Input: ([[[10, 20], [40, 50]], [[15, 25]], [[30, 35]]], 0, 60, 5)
Output: [[0, 10], [25, 30], [35, 40], [50, 60]]

Explanation: These are the gaps where the reduced active meeting count is zero.

Hints

1. Convert each busy interval into two events: +1 at start and -1 at end.
2. After combining events with the same timestamp, sweep from left to right and look for stretches where the active count is zero.

Part 8: Rank and Assign Meeting Rooms by Priority

You manage multiple meeting rooms. Each room starts with its own non-overlapping schedule of existing meetings, though the intervals may be unsorted. For each new meeting request, assign it to one available room using this priority order: fewer meetings already scheduled in that room, then smaller total booked duration in that room, then smaller room id. Intervals are half-open [start, end), so back-to-back meetings are allowed. If no room is available, return -1 for that request. After assignment, the chosen room's schedule and priority stats update before the next request.

Constraints

• 0 <= number of rooms <= 200
• 0 <= total initial meetings <= 20000
• 0 <= number of requests <= 5000
• Within a room, initial meetings do not overlap but may be unsorted
• All intervals satisfy start < end

Examples

Example 1

Input: ({1: [[9, 10], [13, 14]], 2: [[9, 11]], 3: []}, [[10, 11], [11, 12], [13, 14]])
Output: [3, 3, 2]

Explanation: Room 3 is least used for the first two requests. For the third request, room 1 conflicts, so room 2 wins.

Example 2

Input: ({1: [], 2: []}, [[0, 10]])
Output: [1]

Explanation: Edge case: same priority values, so the smaller room id is chosen.

Hints

1. For each room, keep its meetings sorted by start time so availability can be checked quickly.
2. Turn the priority rule into a tuple like (usage_count, total_booked_duration, room_id).