Katkat
Back

Design a task system with assignments

InstacartSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This question tests your ability to design a flexible data model for a task-assignment system, focusing on efficient lookups and state management in an in-memory environment.

Task Assignment System

Design an in-memory task assignment system that manages tasks and their assignments to workers. You are required to support the following operations efficiently:

  1. create_task(task_id, priority): Registers a new task with a given ID and integer priority.
  2. assign_task(task_id, worker_id): Assigns an existing task to a specific worker. A task can only be assigned to one worker at a time.
  3. get_tasks_for_worker(worker_id): Returns all tasks currently assigned to a given worker, ordered by priority (highest priority first).
  4. complete_task(task_id): Marks a task as completed and removes it from the system.

Constraints

  • task_id and worker_id are unique integers.
  • Priority is an integer (higher value means higher priority).
  • The system should handle up to 100,000 tasks and 1,000 workers.

Examples

# Scenario
system = TaskSystem()
system.create_task(101, 5)
system.create_task(102, 10)
system.assign_task(101, 1)
system.assign_task(102, 1)

# get_tasks_for_worker(1) returns [102, 101] (Priority 10 > Priority 5)

Implementation Requirements

Please provide a class structure for TaskSystem with the methods defined above. Consider the time complexity of each operation, specifically focusing on how to maintain the order of tasks per worker.

Hints

Hint 1

Use a hash map to store task metadata and another to map workers to their respective sets of assigned tasks.

Hint 2

A standard list per worker will require re-sorting on every retrieval; consider a data structure that keeps elements sorted upon insertion.

Hint 3

For the complete_task operation, ensure you can efficiently remove the task from both the global storage and the specific worker's assignment list.

Follow-up questions

  • How would you modify the system to support a worker unassigning themselves from a task?
  • If multiple workers could be assigned to the same task, how would your data structures change?
  • How would you handle persistence if the system needs to survive a service restart?