Problem
Design a Todo List Where users can add tasks , mark them as complete , or get a list of pending tasks. Users can also add tags to tasks and can filter the tasks by certain tags.
Implement the TodoList
class:
TodoList()
Initializes the object.int addTask(int userId, String taskDescription, int dueDate, List<String> tags)
Adds a task for the user with the IDuserId
with a due date equal todueDate
and a list of tags attached to the task. The return value is the ID of the task. This ID starts at1
and is sequentially increasing. That is, the first task’s id should be1
, the second task’s id should be2
, and so on.List<String> getAllTasks(int userId)
Returns a list of all the tasks not marked as complete for the user with IDuserId
, ordered by the due date. You should return an empty list if the user has no uncompleted tasks.List<String> getTasksForTag(int userId, String tag)
Returns a list of all the tasks that are not marked as complete for the user with the IDuserId
and havetag
as one of their tags, ordered by their due date. Return an empty list if no such task exists.void completeTask(int userId, int taskId)
Marks the task with the IDtaskId
as completed only if the task exists and the user with the IDuserId
has this task, and it is uncompleted.
Examples
Example 1:
|
|
Constraints:
1 <= userId, taskId, dueDate <= 100
0 <= tags.length <= 100
1 <= taskDescription.length <= 50
1 <= tags[i].length, tag.length <= 20
- All
dueDate
values are unique. - All the strings consist of lowercase and uppercase English letters and digits.
- At most
100
calls will be made for each method.
Solution
Method 1 – Hash Map and Sorting for User Tasks
Intuition
We need to efficiently add, complete, and query tasks for each user, including filtering by tags and ordering by due date. Using a hash map to store user tasks and a global task ID counter allows us to manage tasks efficiently. Sorting by due date ensures correct ordering for queries.
Approach
- Use a global task ID counter, incremented for each new task.
- Store all tasks in a hash map from task ID to task info (userId, description, dueDate, tags, completed).
- For each user, maintain a set of their task IDs.
- For
addTask
, create a new task, store it, and add its ID to the user’s set. - For
getAllTasks
, filter the user’s tasks for uncompleted ones, sort by due date, and return descriptions. - For
getTasksForTag
, filter the user’s uncompleted tasks for the tag, sort by due date, and return descriptions. - For
completeTask
, mark the task as completed if it exists, belongs to the user, and is not already completed.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(nnnxxxnnn)
- 🧺 Space complexity:
O(nnnxxx)