Katkat

Implement timestamped task management system APIs

InstacartSoftware Engineer · Online Assessment

Last updated

This question evaluates a candidate's ability to design and implement time-ordered in-memory data structures and APIs, testing competencies in temporal event ordering and precedence, scheduled deletions, priority-sorted retrieval, user-task assignment, and historical (time-travel) queries.

You are implementing an in-memory Task Management System. All API methods are called with a timestamp representing the logical time when the operation happens.

Assume:

  • API calls are processed in non-decreasing timestamp order.
  • Task IDs and user IDs are strings (or ints).
  • If an operation references a non-existent task/user, it should be a no-op (or return null/false) — choose a consistent behavior and document it.

Data model

Each task has:

  • task_id
  • description
  • priority (integer), default 0 at creation
  • optional assignment to one or more users (define whether multiple users can be assigned; if unspecified, assume a task can be assigned to multiple users and each user can have multiple tasks)

Required APIs

1) CRUD tasks

Implement four methods (all take timestamp):

  • createTask(timestamp, task_id, description)
  • getTask(timestamp, task_id) -> description | null
  • updateTask(timestamp, task_id, new_description)
  • deleteTask(timestamp, task_id)

Deleting a task removes it from the system and unassigns it from all users.

2) Priorities and sorted retrieval

Implement:

  • updateTaskPriority(timestamp, task_id, new_priority)
  • getSortedPrioritizedTasks(timestamp) -> List[task_id]

getSortedPrioritizedTasks should return all currently existing tasks sorted by:

  1. higher priority first
  2. tie-break by task_id ascending (or another deterministic rule you state)

3) Users, assignment, and scheduled deletion

Implement:

  • addUser(timestamp, user_id)
  • assignTaskToUser(timestamp, user_id, task_id)
  • unassignTaskToUser(timestamp, user_id, task_id)
  • scheduleDeletion(timestamp, task_id, delay)

scheduleDeletion schedules the task to be deleted at time timestamp + delay.

Important ordering rule: If one or more deletions are scheduled to occur at time T, then at timestamp T those deletions must be applied before any other operations at the same timestamp T.

4) Time-travel query

Implement:

  • getUserTaskNumsAt(timestamp, user_id, time_at) -> int

This returns the number of tasks assigned to user_id at logical time time_at (where time_at <= timestamp). The result must reflect all creates/deletes/assigns/unassigns/scheduled-deletes that happened up to time_at, with the same deletion-precedence rule at identical timestamps.

Constraints (you may assume)

  • Up to ~200k operations.
  • Timestamps fit in 64-bit integers.
  • Your implementation should be efficient (roughly near O(log n) per operation for the expensive parts).