2590. Design a Todo List
Problem Description
In this problem, we are tasked with designing a Todo List class that simulates a task management system. This system should allow users to add tasks, mark them as complete, and retrieve a list of their pending tasks. Each task can also have tags associated with it, which allows for additional organization and the ability to filter tasks by a specific tag.
Here are the main functionalities that the TodoList
class needs to support:
- Initialization of the TodoList object.
- Addition of tasks, where each task has a unique sequential ID, a textual description, a due date, and a list of tags.
- Retrieval of all uncompleted tasks for a user, sorted by due date.
- Retrieval of all uncompleted tasks for a user that have a specific tag, sorted by due date.
- Completion of a task by marking it as done, provided that the task exists and belongs to the user.
The challenge here is to efficiently handle the addition, completion, and retrieval of tasks for potentially many users while maintaining the ordering of tasks by due date and allowing tag-based filtering.
Intuition
To approach this solution, we need a data structure that can maintain the tasks in sorted order by their due date and facilitate the searching, filtering, and updating of tasks efficiently.
The key components of the design are:
- A hash table (or a default dict in Python), which maps each user's ID to their set of tasks. This structure allows us to quickly access the tasks per user.
- A sorted set to maintain the tasks sorted by due date. This is useful for efficiently retrieving tasks in the desired order.
- Keeping a global task ID counter that increments sequentially as new tasks are added, ensuring unique and sequentially increasing task IDs.
- Representing each task with a list that contains the due date, task description, set of tags, task ID, and a boolean flag indicating whether the task has been completed.
To add a task, we insert it into the user's sorted set of tasks with all the necessary information. Since we are using a sorted set, the due date ordering is maintained automatically. The unique task ID is generated using the global task ID counter.
When retrieving all tasks or tasks by a specific tag, we iterate through the user's set of tasks, selecting those that are not marked as completed. For tag-specific retrieval, we check if the tag is in the set of tags associated with the task.
Finally, to mark a task as complete, we iterate over the user's tasks and update the completion flag for the task with the matching task ID. This change is reflected in place since the tasks are stored as lists and the sorted set merely points to these lists.
Overall, this solution's efficiency stems from the ability of the sorted containers in Python to maintain the order and support fast searching and insertion operations.
Learn more about Sorting patterns.
Solution Approach
The implementation of the TodoList
class in the reference solution uses several algorithms and data structures which are essential to achieve the desired functionalities of adding tasks, retrieving tasks, filtering tasks by tags, and marking tasks as complete.
Here is the breakdown of the solution:
-
Initialization (
__init__
method): We start by initializing an instance variablei
to1
. This variable will serve as the global task ID incrementing sequentially with each new task. We also create atasks
hash table (defaultdict
ofSortedList
). Each key in thetasks
dictionary represents a user's ID and the corresponding value is aSortedList
. TheSortedList
is used because it maintains the ordering of tasks by their due date while still allowing for efficient task retrieval. -
Adding Tasks (
addTask
method): When a new task is added withaddTask
, a new task ID is created from thei
variable. The task information is stored in a list, which includes the due date, task description, a set of tags, the newly created task ID, and a boolean flag for task completion status (initiallyFalse
). This list is added to the sorted list associated with the user's ID in thetasks
dictionary. The sorted list ensures that tasks remain sorted by due date. After inserting the task, the task ID counteri
is incremented, and the new task ID is returned. -
Retrieving All Tasks (
getAllTasks
method): ThegetAllTasks
method iterates through the sorted list of tasks for the user specified byuserId
, and filters out tasks that are not yet completed. It then creates a list containing the descriptions of the pending tasks, preserving the order by due date. This is achieved with a list comprehension that checks the completion status of each task (x[4]
). -
Filtering Tasks by Tag (
getTasksForTag
method): Similarly togetAllTasks
, this method also iterates through the tasks of a particular user, but it includes an additional check to see if the specifiedtag
exists in the set of tags for the task. Tasks that meet both criteria (uncompleted and containing the tag) have their descriptions included in the result list. -
Completing a Task (
completeTask
method): To mark a task as completed, the method iterates over the user's task list, locates the task by the task ID (taskId
), and sets the completion flag toTrue
if the task is found. This marks the task as completed without removing it from the list, which means the task will be omitted when callinggetAllTasks
orgetTasksForTag
.
The aforementioned operations rely heavily on iterating over the sorted set of tasks, but it should be noted that the size of the task set per user could potentially become large. Optimization for marking tasks as completed could be achieved if the data structure allowed direct access to tasks by their ID, which would eliminate the need to iterate over the list; however, in this implementation, such direct access is traded off for simpler code.
In terms of time complexity, adding tasks is O(log n)
due to the insertion into a sorted list, retrieving all tasks or tasks by tag is O(n)
since it involves iterating over all tasks, and completing a task is O(n)
for locating the specific task within the list.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's create an instance of the TodoList
class and walk through each of the functionalities using a simple example:
-
Initialize the TodoList instance:
- Create
todoList = TodoList()
. This initializes thetasks
dictionary and sets the global task IDi
to1
.
- Create
-
Add tasks:
- User with ID
1
adds a task: "Buy groceries" with due date "2023-04-20" and tags['shopping', 'urgent']
.- We call
taskId1 = todoList.addTask(1, "2023-04-20", "Buy groceries", ['shopping', 'urgent'])
. The system returnstaskId1
as1
.
- We call
- Same user adds another task: "Pay bills" with due date "2023-04-22" and a tag
['finance']
.- We call
taskId2 = todoList.addTask(1, "2023-04-22", "Pay bills", ['finance'])
. The system returnstaskId2
as2
.
- We call
- Now, the
tasks
dictionary has one key (user1
) with aSortedList
holding two tasks sorted by due date.
- User with ID
-
Retrieve all uncompleted tasks:
- We call
list1 = todoList.getAllTasks(1)
. This would iterate over theSortedList
for user1
and return a list with descriptions of pending tasks. Since both tasks are uncompleted, it would return["Buy groceries", "Pay bills"]
in sorted order by due date.
- We call
-
Retrieve tasks by a specific tag:
- We want to see all uncompleted shopping tasks for user
1
, so we callshoppingTasks = todoList.getTasksForTag(1, "shopping")
. This would return["Buy groceries"]
, filtering by the tag and ensuring the task is not completed.
- We want to see all uncompleted shopping tasks for user
-
Complete a task:
- User
1
completes the task "Buy groceries". We calltodoList.completeTask(1, taskId1)
. This sets the completion flag for task withtaskId1
toTrue
. - Now if we call
todoList.getAllTasks(1)
again, it would return["Pay bills"]
only, since the "Buy groceries" task has been marked as complete.
- User
In this example, the use of SortedList
ensures that tasks remain sorted by their due date without additional sorting steps each time a query is made. It also illustrates the benefit of storing tasks with completion status and tags, allowing for efficient filtering without affecting the original task list ordering. The encapsulation of task data and operations in the TodoList
class provides a clean interface for managing user tasks.
Solution Implementation
1from collections import defaultdict
2from typing import List, Set, Tuple
3
4class TodoList:
5 def __init__(self):
6 self.task_counter = 1 # Initialize task counter to assign unique IDs to tasks
7 self.tasks = defaultdict(list) # Use a default dictionary to store tasks for each user
8
9 def addTask(
10 self, user_id: int, task_description: str, due_date: int, tags: List[str]
11 ) -> int:
12 """
13 Add a task to the TodoList for a given user. Returns the task ID.
14 :param user_id: Integer representing the user ID.
15 :param task_description: String representing the task description.
16 :param due_date: Integer representing the task's due date.
17 :param tags: List of strings representing the tags associated with the task.
18 :return: Integer representing the newly created task ID.
19 """
20 task_id = self.task_counter
21 self.task_counter += 1
22 # Add the task with its attributes as a tuple to the user's task list
23 self.tasks[user_id].append((due_date, task_description, set(tags), task_id, False))
24 self.tasks[user_id].sort() # Ensure that tasks are sorted by due date
25 return task_id
26
27 def getAllTasks(self, user_id: int) -> List[str]:
28 """
29 Retrieve all incomplete tasks for a given user.
30 :param user_id: Integer representing the user ID.
31 :return: List of strings containing task descriptions for incomplete tasks.
32 """
33 return [task[1] for task in self.tasks[user_id] if not task[4]] # Filter out completed tasks
34
35 def getTasksForTag(self, user_id: int, tag: str) -> List[str]:
36 """
37 Retrieve all incomplete tasks for a given user that have a specified tag.
38 :param user_id: Integer representing the user ID.
39 :param tag: String representing the tag to filter tasks by.
40 :return: List of strings containing task descriptions that match the tag.
41 """
42 # Filter tasks by the specified tag and completion status
43 return [task[1] for task in self.tasks[user_id] if not task[4] and tag in task[2]]
44
45 def completeTask(self, user_id: int, task_id: int) -> None:
46 """
47 Mark a task as complete for a given user.
48 :param user_id: Integer representing the user ID.
49 :param task_id: Integer representing the task ID to be marked as complete.
50 """
51 # Find the task by its ID and mark it as complete
52 for task in self.tasks[user_id]:
53 if task[3] == task_id:
54 task[4] = True
55 break # Once the task is found and marked, exit the loop
56
57# Your TodoList object will be instantiated and called as such:
58# obj = TodoList()
59# param_1 = obj.addTask(user_id,task_description,due_date,tags)
60# param_2 = obj.getAllTasks(user_id)
61# param_3 = obj.getTasksForTag(user_id,tag)
62# obj.completeTask(user_id,task_id)
63
1import java.util.*;
2
3class Task {
4 int id; // Task identifier
5 String name; // Description of the task
6 int dueDate; // Due date for the task
7 Set<String> tags; // A set of tags associated with the task
8 boolean isCompleted; // Flag to indicate if the task is completed
9
10 // Constructor to initialize task properties
11 public Task(int id, String name, int dueDate, Set<String> tags) {
12 this.id = id;
13 this.name = name;
14 this.dueDate = dueDate;
15 this.tags = tags;
16 this.isCompleted = false; // By default, the task is not completed
17 }
18}
19
20class TodoList {
21 private int nextTaskId = 1; // Counter to generate unique task IDs
22 private Map<Integer, TreeSet<Task>> userTasksMap = new HashMap<>(); // Mapping from user ID to a set of tasks
23
24 // TodoList constructor
25 public TodoList() {
26 }
27
28 // Method to add a new task for a user and return the new task ID
29 public int addTask(int userId, String taskDescription, int dueDate, List<String> tags) {
30 // Create a new task object
31 Task newTask = new Task(nextTaskId++, taskDescription, dueDate, new HashSet<>(tags));
32 // Add the task to the user's set of tasks, sorted by due date
33 userTasksMap.computeIfAbsent(userId, k -> new TreeSet<>(Comparator.comparingInt(task -> task.dueDate)))
34 .add(newTask);
35 // Return the assigned task ID
36 return newTask.id;
37 }
38
39 // Method to get all incomplete tasks for a user
40 public List<String> getAllTasks(int userId) {
41 List<String> taskDescriptions = new ArrayList<>();
42 if (userTasksMap.containsKey(userId)) {
43 for (Task task : userTasksMap.get(userId)) {
44 // Check if the task is not completed
45 if (!task.isCompleted) {
46 taskDescriptions.add(task.name);
47 }
48 }
49 }
50 return taskDescriptions;
51 }
52
53 // Method to get all incomplete tasks for a user by a specific tag
54 public List<String> getTasksForTag(int userId, String tag) {
55 List<String> taskDescriptionsForTag = new ArrayList<>();
56 if (userTasksMap.containsKey(userId)) {
57 for (Task task : userTasksMap.get(userId)) {
58 // Check if the task includes the tag and is not completed
59 if (task.tags.contains(tag) && !task.isCompleted) {
60 taskDescriptionsForTag.add(task.name);
61 }
62 }
63 }
64 return taskDescriptionsForTag;
65 }
66
67 // Method to mark a task as completed for a user by task ID
68 public void completeTask(int userId, int taskId) {
69 if (userTasksMap.containsKey(userId)) {
70 for (Task task : userTasksMap.get(userId)) {
71 // Find the task with the given ID and mark it as completed
72 if (task.id == taskId) {
73 task.isCompleted = true;
74 break; // No need to look further as task IDs are unique
75 }
76 }
77 }
78 }
79}
80
81/**
82 * The TodoList class can be used as follows:
83 * TodoList todoList = new TodoList();
84 * int taskId = todoList.addTask(userId, taskDescription, dueDate, tags);
85 * List<String> allTasks = todoList.getAllTasks(userId);
86 * List<String> tasksForTag = todoList.getTasksForTag(userId, tag);
87 * todoList.completeTask(userId, taskId);
88 */
89
1#include <set>
2#include <map>
3#include <string>
4#include <vector>
5#include <algorithm>
6#include <functional>
7
8// Task struct which will store information about each task
9struct Task {
10 int id; // Task identifier
11 std::string name; // Description of the task
12 int dueDate; // Due date for the task
13 std::set<std::string> tags; // A set of tags associated with the task
14 bool isCompleted; // Flag to indicate if the task is completed
15
16 // Constructor to initialize task properties
17 Task(int id, std::string name, int dueDate, const std::set<std::string>& tags)
18 : id(id), name(std::move(name)), dueDate(dueDate), tags(tags), isCompleted(false) {
19 // By default, the task is not completed
20 }
21};
22
23// Comparison function for sorting Tasks by due date
24auto compareTasks = [](const Task& lhs, const Task& rhs) {
25 return lhs.dueDate < rhs.dueDate;
26};
27
28// TodoList class which will manage tasks for each user
29class TodoList {
30private:
31 int nextTaskId = 1; // Counter to generate unique task IDs
32 // Mapping from user ID to a set of tasks, which are sorted by their due date
33 std::map<int, std::set<Task, decltype(compareTasks)>> userTasksMap;
34
35public:
36 // TodoList constructor
37 TodoList() : userTasksMap(compareTasks) {
38 }
39
40 // Method to add a new task for a user and return the new task ID
41 int AddTask(int userId, const std::string& taskDescription, int dueDate, const std::vector<std::string>& tags) {
42 // Create a new task object with a unique ID
43 Task newTask(nextTaskId++, taskDescription, dueDate, std::set<std::string>(tags.begin(), tags.end()));
44 // Add the task to the user's set of tasks
45 userTasksMap[userId].insert(newTask);
46 // Return the newly assigned task ID
47 return newTask.id;
48 }
49
50 // Method to get all incomplete tasks for a user
51 std::vector<std::string> GetAllTasks(int userId) {
52 std::vector<std::string> taskDescriptions;
53 if (userTasksMap.find(userId) != userTasksMap.end()) {
54 for (const Task& task : userTasksMap[userId]) {
55 if (!task.isCompleted) {
56 taskDescriptions.push_back(task.name);
57 }
58 }
59 }
60 return taskDescriptions;
61 }
62
63 // Method to get all incomplete tasks for a user by a specific tag
64 std::vector<std::string> GetTasksForTag(int userId, const std::string& tag) {
65 std::vector<std::string> taskDescriptionsForTag;
66 auto it = userTasksMap.find(userId);
67 if (it != userTasksMap.end()) {
68 for (const Task& task : it->second) {
69 if (task.tags.count(tag) && !task.isCompleted) {
70 taskDescriptionsForTag.push_back(task.name);
71 }
72 }
73 }
74 return taskDescriptionsForTag;
75 }
76
77 // Method to mark a task as completed for a user by task ID
78 void CompleteTask(int userId, int taskId) {
79 auto it = userTasksMap.find(userId);
80 if (it != userTasksMap.end()) {
81 auto& tasks = it->second;
82 auto taskIt = std::find_if(tasks.begin(), tasks.end(), [taskId](const Task& task) { return task.id == taskId; });
83 if (taskIt != tasks.end()) {
84 taskIt->isCompleted = true;
85 }
86 }
87 }
88};
89
90/**
91 * The TodoList class can be used as follows:
92 * TodoList todoList;
93 * int taskId = todoList.AddTask(userId, taskDescription, dueDate, tags);
94 * std::vector<std::string> allTasks = todoList.GetAllTasks(userId);
95 * std::vector<std::string> tasksForTag = todoList.GetTasksForTag(userId, tag);
96 * todoList.CompleteTask(userId, taskId);
97 */
98
1interface Task {
2 id: number;
3 name: string;
4 dueDate: number;
5 tags: Set<string>;
6 isCompleted: boolean;
7}
8
9// Comparator function for sorting tasks by due date
10function sortByDueDate(a: Task, b: Task) : number {
11 return a.dueDate - b.dueDate;
12}
13
14let nextTaskId = 1; // Counter to generate unique task IDs
15let userTasksMap: Map<number, Set<Task>> = new Map(); // Mapping from user ID to a set of tasks
16
17// Adds a new task for a user and returns the new task ID
18function addTask(userId: number, taskDescription: string, dueDate: number, tags: string[]): number {
19 const newTask: Task = {
20 id: nextTaskId++,
21 name: taskDescription,
22 dueDate: dueDate,
23 tags: new Set(tags),
24 isCompleted: false // By default, the task is not completed
25 };
26
27 // Add the task to the user's set of tasks, sorted by due date
28 const tasks = userTasksMap.get(userId) || new Set<Task>();
29 tasks.add(newTask);
30 userTasksMap.set(userId, tasks);
31
32 return newTask.id;
33}
34
35// Gets all incomplete tasks for a user
36function getAllTasks(userId: number): string[] {
37 const tasks: string[] = [];
38 const userTasks = userTasksMap.get(userId);
39 if (userTasks) {
40 for (let task of Array.from(userTasks).sort(sortByDueDate)) {
41 if (!task.isCompleted) {
42 tasks.push(task.name);
43 }
44 }
45 }
46 return tasks;
47}
48
49// Gets all incomplete tasks for a user by a specific tag
50function getTasksForTag(userId: number, tag: string): string[] {
51 const tasksForTag: string[] = [];
52 const userTasks = userTasksMap.get(userId);
53 if (userTasks) {
54 for (let task of Array.from(userTasks).sort(sortByDueDate)) {
55 if (!task.isCompleted && task.tags.has(tag)) {
56 tasksForTag.push(task.name);
57 }
58 }
59 }
60 return tasksForTag;
61}
62
63// Marks a task as completed for a user by task ID
64function completeTask(userId: number, taskId: number): void {
65 const userTasks = userTasksMap.get(userId);
66 if (userTasks) {
67 for (let task of userTasks) {
68 // Find the task with the given ID and mark it as completed
69 if (task.id === taskId) {
70 task.isCompleted = true;
71 break; // No need to look further as task IDs are unique
72 }
73 }
74 }
75}
76
Time and Space Complexity
Time Complexity
-
addTask()
has a time complexity ofO(log n)
for a particular user wheren
is the number of tasks of that user, because it involves adding a task to theSortedList
, which takes logarithmic time for insertion. -
getAllTasks()
has a time complexity ofO(m)
, wherem
is the number of incomplete tasks for the user, since it requires iterating through all tasks to filter out completed ones and collect descriptions. -
getTasksForTag()
also has a time complexity ofO(m)
, wherem
is again the number of incomplete tasks for the user. This is because it filters tasks by a specific tag. -
completeTask()
has a time complexity ofO(m)
wherem
is the number of tasks of a user. In the worst case, it involves iterating through all the tasks to find the one with the specified taskId.
Space Complexity
- The overall space complexity of the
TodoList
class isO(n)
, wheren
is the total number of all tasks across all users. This accounts for the storage of task details (due date, description, tags, taskId, and completion status) in the tasks data structure.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.