Implement timestamped task management system APIs
You are tasked with implementing an in-memory Task Management System. All API methods are invoked with a timestamp parameter, which represents the logical time at which the operation occurs.
Assumptions
- API calls are guaranteed to be processed in non-decreasing
timestamporder. - Task IDs and user IDs are strings (or integers).
- If an operation references a non-existent task or user, it should be a no-op (or return null/false). The chosen consistent behavior must be documented.
Data Model
Each task entity must include:
task_id(unique identifier)descriptionpriority(integer), defaulting to0upon creation.- Optional assignment to one or more users. A task can be assigned to multiple users, and each user can have multiple tasks.
Required APIs
1) CRUD Tasks
Implement the following four methods, each accepting a timestamp:
createTask(timestamp, task_id, description)getTask(timestamp, task_id) -> description | nullupdateTask(timestamp, task_id, new_description)deleteTask(timestamp, task_id)
Deleting a task must remove it entirely from the system and unassign 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:
- Higher
priorityfirst. - Tie-break by
task_idascending (or another deterministic rule you define).
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 specified task for deletion at logical time timestamp + delay.
Important Ordering Rule: If one or more deletions are scheduled to occur at time T, these 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 method must return the number of tasks assigned to user_id at the specified logical time time_at (where time_at <= timestamp). The result must accurately reflect all creates, deletes, assigns, unassigns, and scheduled deletions that occurred up to time_at, adhering to the same deletion-precedence rule for identical timestamps.
Constraints
You may assume the following:
- Up to approximately 200,000 operations.
- Timestamps will fit within 64-bit integers.
- Your implementation should be efficient, aiming for roughly O(log n) per operation for the most complex parts.
AI interview prep
Core dilemma
Efficiently managing and querying temporal state, specifically handling out-of-order logical time queries (`time_at`) and complex event ordering (scheduled deletion precedence) within an `in-memory` system, while maintaining O(log N) performance.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Implement timestamped task management system APIs
You are tasked with implementing an in-memory Task Management System. All API methods are invoked with a timestamp parameter, which represents the logical time at which the operation occurs.
Assumptions
- API calls are guaranteed to be processed in non-decreasing
timestamporder. - Task IDs and user IDs are strings (or integers).
- If an operation references a non-existent task or user, it should be a no-op (or return null/false). The chosen consistent behavior must be documented.
Data Model
Each task entity must include:
task_id(unique identifier)descriptionpriority(integer), defaulting to0upon creation.- Optional assignment to one or more users. A task can be assigned to multiple users, and each user can have multiple tasks.
Required APIs
1) CRUD Tasks
Implement the following four methods, each accepting a timestamp:
createTask(timestamp, task_id, description)getTask(timestamp, task_id) -> description | nullupdateTask(timestamp, task_id, new_description)deleteTask(timestamp, task_id)
Deleting a task must remove it entirely from the system and unassign 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:
- Higher
priorityfirst. - Tie-break by
task_idascending (or another deterministic rule you define).
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 specified task for deletion at logical time timestamp + delay.
Important Ordering Rule: If one or more deletions are scheduled to occur at time T, these 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 method must return the number of tasks assigned to user_id at the specified logical time time_at (where time_at <= timestamp). The result must accurately reflect all creates, deletes, assigns, unassigns, and scheduled deletions that occurred up to time_at, adhering to the same deletion-precedence rule for identical timestamps.
Constraints
You may assume the following:
- Up to approximately 200,000 operations.
- Timestamps will fit within 64-bit integers.
- Your implementation should be efficient, aiming for roughly O(log n) per operation for the most complex parts.