Katkat
Back

Assign tasks to workers with types and accounts

StripeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to manage task scheduling with specific affinity constraints and varying worker processing times using an efficient priority-based simulation.

Task Assignment System

You are building a task scheduler for a platform where tasks must be assigned to the most suitable available worker. You are given a list of tasks and a set of available workers.

Rules:

  1. Each Task has a task_id, account_id, and processing_time.
  2. Each Worker has a worker_id and a type. Some workers are 'General', while others are 'Specialized'.
  3. Affinity Constraint: If a task has an account_id that has been assigned to a worker previously, that task should ideally be routed back to that same worker to maintain data locality, provided that worker is free.
  4. Efficiency: Workers process tasks one at a time. A worker becomes available again at current_time + processing_time.

Implement a scheduler function that assigns a sequence of incoming tasks to workers. If multiple workers are free at the same time, pick the worker with the lowest worker_id.

Interface

def schedule_tasks(tasks, workers):
    # tasks: list of dicts {'task_id': int, 'account_id': int, 'processing_time': int}
    # workers: list of dicts {'worker_id': int, 'type': str}
    # Returns: list of dicts {'task_id': int, 'worker_id': int, 'finish_time': int}

Examples

Input: Tasks: [{'task_id': 1, 'account_id': 100, 'processing_time': 5}, {'task_id': 2, 'account_id': 100, 'processing_time': 3}] Workers: [{'worker_id': 1, 'type': 'General'}, {'worker_id': 2, 'type': 'General'}]

Output: [{'task_id': 1, 'worker_id': 1, 'finish_time': 5}, {'task_id': 2, 'worker_id': 1, 'finish_time': 8}] (Task 2 is assigned to Worker 1 because of account affinity.)

Constraints

  • 1 <= len(tasks) <= 10^5
  • 1 <= len(workers) <= 1000
  • All processing_time values are positive integers.

Hints

Hint 1

Use a min-priority queue to track worker availability times to always pick the earliest available worker.

Hint 2

Maintain a hash map to keep track of the last worker assigned to each `account_id`.

Hint 3

When a task arrives, first check if the previously assigned worker is available; if not, fall back to the global min-priority queue of idle workers.

Follow-up questions

  • How would you modify your solution if workers had different processing speeds (e.g., a 'Specialized' worker processes tasks 2x faster)?
  • What changes are needed if tasks have deadlines, and we must minimize the number of missed deadlines?
  • How would you handle the case where the number of tasks is significantly larger than the number of workers and we need to process them in a distributed environment?