How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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.

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:

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

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:

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

Assign tasks to workers with types and accounts

Quick Overview

Assign tasks to workers with types and accounts

Assignment rules

Output

Constraints (for efficiency expectations)

Submit Your Answer to Earn 20XP

Assign tasks to workers with types and accounts

Quick Overview

Assign tasks to workers with types and accounts

Assignment rules

Output

Constraints (for efficiency expectations)

Submit Your Answer to Earn 20XP