Watch 10 video solutions for Design a Todo List, a medium level problem involving Array, Hash Table, String. This walkthrough by Ashish Pratap Singh has 1,177,663 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 ID userId with a due date equal to dueDate and a list of tags attached to the task. The return value is the ID of the task. This ID starts at 1 and is sequentially increasing. That is, the first task's id should be 1, the second task's id should be 2, and so on.List<String> getAllTasks(int userId) Returns a list of all the tasks not marked as complete for the user with ID userId, 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 ID userId and have tag 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 ID taskId as completed only if the task exists and the user with the ID userId has this task, and it is uncompleted.
Example 1:
Input
["TodoList", "addTask", "addTask", "getAllTasks", "getAllTasks", "addTask", "getTasksForTag", "completeTask", "completeTask", "getTasksForTag", "getAllTasks"]
[[], [1, "Task1", 50, []], [1, "Task2", 100, ["P1"]], [1], [5], [1, "Task3", 30, ["P1"]], [1, "P1"], [5, 1], [1, 2], [1, "P1"], [1]]
Output
[null, 1, 2, ["Task1", "Task2"], [], 3, ["Task3", "Task2"], null, null, ["Task3"], ["Task3", "Task1"]]
Explanation
TodoList todoList = new TodoList();
todoList.addTask(1, "Task1", 50, []); // return 1. This adds a new task for the user with id 1.
todoList.addTask(1, "Task2", 100, ["P1"]); // return 2. This adds another task for the user with id 1.
todoList.getAllTasks(1); // return ["Task1", "Task2"]. User 1 has two uncompleted tasks so far.
todoList.getAllTasks(5); // return []. User 5 does not have any tasks so far.
todoList.addTask(1, "Task3", 30, ["P1"]); // return 3. This adds another task for the user with id 1.
todoList.getTasksForTag(1, "P1"); // return ["Task3", "Task2"]. This returns the uncompleted tasks that have the tag "P1" for the user with id 1.
todoList.completeTask(5, 1); // This does nothing, since task 1 does not belong to user 5.
todoList.completeTask(1, 2); // This marks task 2 as completed.
todoList.getTasksForTag(1, "P1"); // return ["Task3"]. This returns the uncompleted tasks that have the tag "P1" for the user with id 1.
// Notice that we did not include "Task2" because it is completed now.
todoList.getAllTasks(1); // return ["Task3", "Task1"]. User 1 now has 2 uncompleted tasks.
Constraints:
1 <= userId, taskId, dueDate <= 1000 <= tags.length <= 1001 <= taskDescription.length <= 501 <= tags[i].length, tag.length <= 20dueDate values are unique.100 calls will be made for each method.Problem Overview: Design a Todo List system that supports adding tasks, marking tasks as completed, and retrieving a user’s pending tasks filtered by tags. Returned tasks must be ordered by due date. The challenge is maintaining fast updates while keeping tasks sorted.
Approach 1: Hash Table + On-Demand Sorting (Add O(1), Query O(n log n))
Store all tasks in a hash table keyed by userId. Each user maps to a list or array of tasks containing taskId, dueDate, tags, and completion status. Adding a task is constant time since you simply append to the user’s list. When fetching tasks, iterate through the list, filter out completed tasks and tasks without the requested tag, then sort the remaining tasks by dueDate using a sorting algorithm.
This approach is simple and easy to implement, but retrieval becomes expensive as the number of tasks grows. Every query requires scanning all tasks and performing a sort. For large task lists or frequent queries, the O(n log n) query cost becomes the bottleneck.
Approach 2: Hash Table + Sorted Set (Add O(log n), Query O(k + log n))
Maintain a hash table mapping each userId to a sorted structure keyed by dueDate. A sorted set (or TreeSet / balanced BST) keeps tasks ordered automatically. Each entry stores dueDate and taskId so ordering is preserved without running a full sort. Another hash table tracks task metadata (tags and completion state) for quick lookup.
When you add a task, insert it into the user’s sorted set. The structure ensures tasks remain ordered by dueDate in O(log n) time. Completing a task simply updates its status in the metadata table. When retrieving tasks, iterate through the sorted set from earliest dueDate, skip completed tasks, and filter by tag. Since the structure is already sorted, no additional sorting step is required.
This design separates ordering from metadata storage. The sorted set handles ordering efficiently, while the hash map provides constant-time lookups for task details. The result is predictable performance even with many tasks.
Recommended for interviews: The Hash Table + Sorted Set design is the expected solution. It demonstrates understanding of system design tradeoffs and efficient data structures. A brute-force list with sorting shows baseline reasoning, but the sorted structure proves you can optimize repeated queries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table + On-Demand Sorting | Add: O(1), Query: O(n log n) | O(n) | Small datasets or when queries are rare |
| Hash Table + Sorted Set | Add: O(log n), Query: O(k + log n) | O(n) | Frequent queries where tasks must stay ordered by due date |