Quick Overview

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.

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.

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

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.

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

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.

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

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.

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

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.

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

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

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

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.

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

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.

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)`.

Loading coding console...