How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Implement rate limiter, top-K, scheduler algorithms

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### 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.

Quick Answer: This question evaluates proficiency in concurrent programming and thread-safe design, core algorithm implementation (binary search and top-K logic), data structure usage (including doubly-linked-list techniques), and scheduling and ranking reasoning for meeting and resource allocation.

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

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

Expected 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.

Input: (1, 10, [5, 5])

Expected Output: [True, False]

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

Input: (1, 10, [1, 11])

Expected Output: [True, True]

Explanation: At time 11, the request from time 1 has just expired because the window is `(1, 11]`.

Input: (2, 5, [])

Expected Output: []

Explanation: Edge case: no requests.

Hints

Only accepted requests inside the current time window matter.
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

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

Expected 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.

Input: (1, 3, [[], [1, 1], [4]])

Expected Output: [[], [True, False], [True]]

Explanation: Edge case: one thread has no requests.

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

Expected Output: [[True, True], [True], [False]]

Explanation: At timestamp 5, thread 0 is processed before thread 2, so thread 0 gets the last available slot.

Input: (1, 10, [[3], [3], [3]])

Expected Output: [[True], [False], [False]]

Explanation: With identical timestamps, smaller thread index wins.

Hints

This is like merging k sorted lists while maintaining one shared sliding window.
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

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

Expected Output: [True, True, False, True]

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

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

Expected Output: []

Explanation: Edge case: no `allow` operations.

Input: (1, 3, [('allow',), ('advance', 3), ('allow',), ('allow',)])

Expected Output: [True, True, False]

Explanation: At time 3, the request from time 0 has expired, but the second request at time 3 fills the window.

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

Expected Output: [True, True, True, True]

Explanation: The request at time 0 expires before the two requests at time 2 are checked.

Hints

Treat `allow` as reading from stored state, not from a parameter.
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

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

Expected Output: 1

Explanation: The first 2 appears at index 1.

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

Expected Output: -1

Explanation: The target is not present.

Input: ([], 10)

Expected Output: -1

Explanation: Edge case: empty array.

Input: ([5], 5)

Expected Output: 0

Explanation: Single-element match.

Input: ([1, 1, 1], 1)

Expected Output: 0

Explanation: All elements match, so the first index is 0.

Hints

When you find the target, do not stop immediately if duplicates may exist.
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

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

Expected Output: [2, 5]

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

Input: ([], 3)

Expected Output: []

Explanation: Edge case: empty stream.

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

Expected Output: [1, 2, 3]

Explanation: All values have the same frequency, so return them in ascending order.

Input: ([4, 4, -1, -1, -1, 2, 2, 2], 3)

Expected Output: [-1, 2, 4]

Explanation: The top frequencies are -1 and 2 with 3 each, then 4 with 2.

Hints

Move an element only from frequency f to frequency f + 1 as you process the stream.
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

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

Expected Output: [[570, 585], [615, 630], [660, 720]]

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

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

Expected Output: [[150, 180]]

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

Input: ([[], []], [[0, 30], [40, 60]], 10)

Expected Output: []

Explanation: Edge case: the working bounds do not overlap.

Input: ([[], []], [[60, 180], [90, 150]], 20)

Expected Output: [[90, 150]]

Explanation: With no busy intervals, the full overlap of the work bounds is available.

Hints

First reduce the search space to the intersection of all working bounds.
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

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

Expected Output: [[720, 780]]

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

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

Expected Output: [[0, 10], [25, 30], [35, 40], [50, 60]]

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

Input: ([], 0, 10, 3)

Expected Output: [[0, 10]]

Explanation: Edge case: no busy intervals at all.

Input: ([[[-5, 2], [8, 12]], [[2, 4], [6, 8]]], 0, 10, 2)

Expected Output: [[4, 6]]

Explanation: Intervals are clipped to the day bounds, then touching intervals merge through the event sweep.

Hints

Convert each busy interval into two events: +1 at start and -1 at end.
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

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

Expected 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.

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

Expected Output: [1]

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

Input: ({1: [[0, 5]], 2: [[1, 4]]}, [[2, 3], [5, 6]])

Expected Output: [-1, 2]

Explanation: The first request fits nowhere. For the second, both rooms are available, so room 2 wins because it has less total booked time.

Input: ({1: [[0, 30]], 2: [[0, 10], [20, 30]], 3: [[5, 15]]}, [[15, 20], [30, 40]])

Expected Output: [3, 1]

Explanation: Priority values change after each assignment.

Hints

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