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 Technical Screen rounds at Stripe.

What role is this question designed for?

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

Assign tasks to workers with types and accounts

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are implementing a task scheduler. There are `W` workers (IDs `0..W-1`) and `N` tasks (IDs `0..N-1`). Each task `i` arrives at time `arrival[i]` (non-decreasing) and has: - `duration[i]` (positive integer) - `type[i]` (string or integer label) - `account[i]` (string or integer label) Each worker `w` has: - a set `skills[w]` of task types it can process - a processing speed per type `speed[w][t]` (positive integer). If `t ∉ skills[w]`, the worker cannot run that task. When worker `w` runs task `i` of type `t`, the runtime is: \[ runTime(w,i) = duration[i] \times speed[w][t] \] A worker can process at most one task at a time. If a worker starts a task at time `s`, it becomes free again at time `s + runTime`. ### Assignment rules Process tasks in increasing task index `i = 0..N-1` (i.e., by arrival order). For each task, choose a worker using these rules: 1. **Account stickiness (Part 3):** Maintain a mapping `owner[account] -> workerId` for accounts that have been assigned before. - If `owner[account[i]] = w` exists **and** `w` supports `type[i]`, then task `i` must be assigned to `w`. - If the mapped worker does **not** support `type[i]`, ignore stickiness for this task and use Rule 2. 2. **Fastest eligible worker (Part 2):** Among workers that support `type[i]`, assign the task to the worker that will **finish it earliest**, assuming it starts as soon as possible: - Earliest start time for worker `w` is `start = max(arrival[i], nextFreeTime[w])`. - Finish time is `finish = start + runTime(w,i)`. - Choose the worker with minimum `(finish, workerId)` lexicographically (tie-break by smaller `workerId`). 3. **Update ownership:** After assigning task `i` to worker `w`, set `owner[account[i]] = w`. ### Output Return an array `assigned[i] = workerId` indicating which worker each task is assigned to. ### Constraints (for efficiency expectations) Assume up to `W, N ≤ 2e5`, and total number of `(worker,type)` skill entries can be large. Your solution should be efficient (e.g., avoid scanning all workers per task).

Quick Answer: This question evaluates algorithmic scheduling and dynamic resource-allocation skills, including priority-queue/heap usage, time-based simulation, and scalable data-structure design for account affinity and heterogeneous worker speeds.

Part 1: Fastest Eligible Task Assignment

You are implementing a simple task scheduler. There are W workers with IDs 0 through W - 1 and N tasks with IDs 0 through N - 1. Tasks are processed in increasing index order. Task i arrives at arrival[i], takes base duration duration[i], and has type task_type[i]. Each worker w has a dictionary worker_speeds[w] mapping supported task types to a positive speed multiplier. If type t is absent from worker_speeds[w], worker w cannot process tasks of type t. If worker w runs task i of type t, the runtime is duration[i] * worker_speeds[w][t]. A worker can process at most one task at a time. For each task, assign it to an eligible worker that gives the earliest finish time if started as soon as possible. For worker w, start = max(arrival[i], next_free[w]) and finish = start + runtime. Choose the worker with the smallest pair (finish, workerId). After assigning the task, update that worker's next free time to the finish time.

Constraints

0 <= N <= 5000
0 <= W <= 5000
N * W <= 2000000
arrival is non-decreasing
duration[i] is a positive integer for every task
All speed multipliers are positive integers
Every task has at least one eligible worker
Task type labels are strings

Examples

Input: ([0, 1, 2], [5, 2, 1], ['A', 'A', 'B'], [{'A': 1, 'B': 5}, {'A': 2}, {'B': 1}])

Expected Output: [0, 1, 2]

Explanation: Task 0 goes to worker 0 because it finishes at 5. Task 1 goes to worker 1 because worker 0 is busy until 5. Task 2 goes to worker 2 because it is much faster for B.

Input: ([0, 0], [2, 1], ['X', 'X'], [{'X': 2}, {'X': 2}, {'X': 3}])

Expected Output: [0, 1]

Explanation: For task 0, workers 0 and 1 both finish at time 4, so worker 0 wins by ID. For task 1, worker 1 is free and finishes earliest.

Input: ([0, 0, 3], [10, 4, 1], ['A', 'A', 'A'], [{'A': 1}, {'A': 3}])

Expected Output: [0, 1, 0]

Explanation: Worker 0 is faster but becomes busy after task 0. Worker 1 gets task 1 because it can finish earlier. Worker 0 gets task 2 because it still finishes before worker 1.

Input: ([0, 1, 1, 10], [3, 2, 4, 1], ['A', 'B', 'A', 'B'], [{'A': 2}, {'B': 1}, {'A': 1, 'B': 3}])

Expected Output: [2, 1, 2, 1]

Explanation: Different task types have different eligible worker sets. Each task is assigned using earliest finish time among workers that support its type.

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

Expected Output: []

Explanation: There are no tasks, so no assignments are made.

Hints

Maintain an array next_free where next_free[w] is the earliest time worker w can start a new task.
For each eligible worker, compute finish and compare the tuple (finish, workerId).

Part 2: Account-Sticky Task Assignment

Extend the task scheduler with account stickiness. There are W workers and N tasks processed in increasing index order. Task i has arrival time arrival[i], base duration duration[i], type task_type[i], and account account[i]. Each worker w supports the task types present as keys in worker_speeds[w], with positive speed multiplier worker_speeds[w][t]. Runtime is duration[i] * worker_speeds[w][t]. Maintain a mapping owner from account to worker. For task i, if owner[account[i]] exists and that worker supports task_type[i], assign the task to that owner worker even if another worker could finish earlier. If the owner does not exist or does not support the task type, fall back to choosing the eligible worker with minimum (finish, workerId), where finish is computed using start = max(arrival[i], next_free[w]). After every successful assignment, set owner[account[i]] to the chosen worker.

Constraints

0 <= N <= 5000
0 <= W <= 5000
N * W <= 2000000
arrival is non-decreasing
duration[i] is a positive integer for every task
All speed multipliers are positive integers
Every task has at least one eligible worker
Task type labels and account labels are strings

Examples

Input: ([0, 1, 2], [5, 2, 1], ['A', 'A', 'A'], ['acct', 'acct', 'other'], [{'A': 1}, {'A': 2}])

Expected Output: [0, 0, 1]

Explanation: Task 0 assigns account acct to worker 0. Task 1 must also go to worker 0 due to stickiness, even though worker 1 could finish earlier. Task 2 has a different account and goes to worker 1.

Input: ([0, 1, 2, 3], [4, 2, 1, 1], ['A', 'B', 'B', 'A'], ['x', 'x', 'x', 'x'], [{'A': 1}, {'B': 1}, {'A': 2, 'B': 3}])

Expected Output: [0, 1, 1, 0]

Explanation: Account x first maps to worker 0. Worker 0 cannot process B, so task 1 falls back to worker 1 and remaps x. Task 2 sticks to worker 1. Worker 1 cannot process A, so task 3 falls back and chooses worker 0 by the finish-time then ID rule.

Input: ([0, 0, 1], [10, 1, 1], ['A', 'A', 'A'], ['a', 'b', 'a'], [{'A': 1}, {'A': 1}])

Expected Output: [0, 1, 0]

Explanation: Account a is owned by worker 0 after task 0. Task 2 must wait for worker 0 due to stickiness, even though worker 1 is free.

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

Expected Output: []

Explanation: There are no tasks, so the owner map remains empty and no assignments are returned.

Hints

Before doing the fastest-worker scan, check whether the task's account already has an owner that supports the task type.
When fallback assignment is used because the previous owner is missing or unsupported, overwrite the owner mapping with the newly chosen worker.

Quick Overview

This question evaluates algorithmic scheduling and dynamic resource-allocation skills, including priority-queue/heap usage, time-based simulation, and scalable data-structure design for account affinity and heterogeneous worker speeds.