Quick Overview

Schedule arriving seller tasks by per-seller priority and FIFO order while rotating fairly across sellers. The exercise adds tier weights, seller activation and reactivation, empty queues, null processing results, and persistent turn state across interleaved operations.

Schedule Seller Tasks with Tier-Weighted Round Robin

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

# Schedule Seller Tasks with Tier-Weighted Round Robin Implement `scheduleSellerTasks(operations)`. Tasks arrive over time and belong to sellers. Each task has a unique `taskId`, a `sellerId`, a seller tier, and a priority. Process operations in order and return the selected seller and task for every process request. Each operation is an array of strings: - `["receive", taskId, sellerId, tier, priority]` adds a task. `tier` is `VIP` or `STANDARD`; `priority` is `1`, `2`, or `3`, where `1` is highest. - `["process"]` selects the next task and returns `[sellerId, taskId]`, or `null` if no task is pending. ## Scheduling Rules - Within one seller, process lower numeric priority first. Tasks with the same priority use their receive order. - Active sellers take turns in the order they first became nonempty. - A `STANDARD` seller may process one task in its turn. A `VIP` seller may process up to two consecutive tasks in its turn. - If a seller becomes empty before using its quota, its turn ends immediately. - After using its quota, a still-nonempty seller moves to the back of the active-seller order. - A seller that becomes nonempty while absent from the active order joins its back. - A seller's tier is consistent across all of its tasks. ## Constraints - `1 <= operations.length <= 200,000` - Task and seller IDs contain 1 to 50 English letters or digits. - Task IDs are globally unique. - Return results in process-operation order. ## Example 1 ```text Input: operations = [["receive", "a1", "A", "VIP", "2"], ["receive", "b1", "B", "STANDARD", "1"], ["receive", "a2", "A", "VIP", "1"], ["process"], ["process"], ["process"]] Output: [["A", "a2"], ["A", "a1"], ["B", "b1"]] ``` Seller `A` uses both VIP slots, while its priority-1 task precedes its earlier priority-2 task. ## Example 2 ```text Input: operations = [["receive", "a1", "A", "VIP", "1"], ["receive", "b1", "B", "STANDARD", "2"], ["process"], ["receive", "a2", "A", "VIP", "1"], ["process"], ["receive", "b2", "B", "STANDARD", "1"], ["process"], ["process"]] Output: [["A", "a1"], ["B", "b1"], ["A", "a2"], ["B", "b2"]] ``` When `A` becomes empty, its first turn ends. Its new task later rejoins behind already-active seller `B`.

Overview: Schedule arriving seller tasks by per-seller priority and FIFO order while rotating fairly across sellers. The exercise adds tier weights, seller activation and reactivation, empty queues, null processing results, and persistent turn state across interleaved operations.

Read the full TikTok Software Engineer interview experience this question came from

Implement scheduleSellerTasks(operations). A receive operation supplies a unique taskId, sellerId, seller tier (VIP or STANDARD), and priority 1, 2, or 3, with 1 highest. A process operation returns [sellerId, taskId] or null when no task is pending. Within a seller, lower numeric priority runs first and equal priorities retain receive order. Active sellers take turns in the order they first became nonempty. STANDARD gets one task per turn; VIP gets up to two consecutive tasks. A seller that empties ends its turn, a still-nonempty seller moves to the back after its quota, and a seller that later becomes nonempty rejoins at the back.

Constraints

  • 1 <= operations.length <= 200,000
  • Task IDs and seller IDs contain 1 to 50 English letters or digits.
  • Task IDs are globally unique.
  • Each tier is VIP or STANDARD, and a seller's tier is consistent across its tasks.
  • Each priority is the string 1, 2, or 3, where 1 is highest.
  • Return one result for each process operation in operation order.

Examples

Input: ([['process']],)

Expected Output: [None]

Explanation: A process request returns null when no task is pending.

Input: ([['receive', 't1', 'S', 'STANDARD', '2'], ['process'], ['process']],)

Expected Output: [['S', 't1'], None]

Explanation: A single standard seller supplies one task and then the scheduler is empty.

Hints

  1. Separate the order among sellers from the priority order within one seller.
  2. A fixed set of three FIFO queues can preserve both task priority and receive-order ties.
  3. Remember how much of the seller at the front's current tier quota has been used.

Loading coding console...

Show the approach

Approach

Keep three FIFO queues per seller, one for each priority, and a global deque of active seller IDs. The front seller owns the current turn. Select from its first nonempty priority queue and count how many slots of the current tier quota have been used. Remove an empty seller immediately; otherwise rotate it to the back when its quota is consumed. On receive, append the seller to the active deque only when it was absent. This separates seller fairness from priority order inside each seller.

Time complexity:
O(m) expected time for m operations, because there are only three priority queues and every receive, process, activation, and rotation uses constant expected time.
Space complexity:
O(t + s + p), where t is the number of received tasks retained in queues, s is the number of known sellers, and p is the number of process results.