Design a Todo List

Medium

Asked by:

4 views

Topics:

ArraysStringsHash TableDesign

Design a Todo List data structure that performs the following operations:

addTodo(todoId, userId, content): Adds a todo to the todo list.
getTodos(userId): Retrieves all todos for a specific user. Each todo should contain the todoId and content.
deleteTodo(todoId): Deletes a specific todo from the todo list.

Implement the TodoList class:

TodoList() Initializes the TodoList object.
void addTodo(int todoId, int userId, String content) Adds a todo to the todo list.
List<List<String>> getTodos(int userId) Retrieves all todos for a specific user. The outer list represents a list of todos, and each inner list contains the todoId (converted to a string) and the content. The order of todos in the list should be based on the order they were added.
void deleteTodo(int todoId) Deletes a specific todo from the todo list.

Example:

TodoList todoList = new TodoList();
todoList.addTodo(1, 1, "Write a blog post");
todoList.addTodo(2, 1, "Read a book");
todoList.addTodo(3, 2, "Buy groceries");
System.out.println(todoList.getTodos(1)); // Output: [["1", "Write a blog post"], ["2", "Read a book"]]
todoList.deleteTodo(2);
System.out.println(todoList.getTodos(1)); // Output: [["1", "Write a blog post"]]
System.out.println(todoList.getTodos(2)); // Output: [["3", "Buy groceries"]]

Constraints:

1 <= todoId, userId <= 10⁵
1 <= content.length <= 50
content consists of English letters, digits, and spaces.
todoId are unique.
At most 10⁵ calls will be made to addTodo, getTodos, and deleteTodo.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior for `deleteTodo` if the provided `todoId` does not exist? Should the operation fail silently?
If `getTodos` is called for a `userId` that has no todos or has never been associated with any todos, should the method return an empty list or `null`?
Regarding the uniqueness of `todoId`, does this constraint hold even after a todo is deleted? For instance, can a `todoId` be reused in a future `addTodo` call once its original todo has been deleted?
Although the problem states `todoId`s are unique, how should the system handle an `addTodo` call with a `todoId` that is already in use? Should it update the existing todo, or can I assume this scenario will never occur?
The problem requires `getTodos` to return todos in the order they were added. If a user's todos are added, then some are deleted, and then new ones are added, should the new todos be appended to the end of the existing, ordered list for that user?

Brute Force Solution

Approach

The simplest way to build a todo list is to think of it as a single, unorganized list of notes written on a piece of paper. To do anything with a specific note, like crossing it off or changing it, you have to read through the entire list from the very beginning until you find the right one.

Here's how the algorithm would work step-by-step:

First, imagine you have a single, empty container to hold all of your tasks.
When you want to add a new task, you simply place it into the container without worrying about any specific order.
If you want to view all your tasks, you look at every single item in the container, one after another.
Now, if you need to find a specific task to either edit, delete, or mark as complete, you must start your search from the very first task in the container.
You check that first task to see if it's the one you're looking for.
If it's not, you move on to the second task and check it, then the third, and so on, repeating this for every task.
You continue this process of checking every single item until you finally find the one you need.
Once you've found the correct task, you can then perform your action, like changing its description or marking it as done.

Code Implementation

class TodoList:
    def __init__(self):
        # All tasks are kept in a simple list, preserving the order of addition.

        self.tasks_list = []

    def add_task(self, task_description):
        new_task = {
            'description': task_description,
            'status': 'incomplete'
        }
        self.tasks_list.append(new_task)

    def mark_task_complete(self, description_to_find):
        # To change a task, we must scan from the start until we find the matching one.

        for current_task in self.tasks_list:
            if current_task['description'] == description_to_find:
                current_task['status'] = 'complete'
                return True
        return False

    def delete_task(self, description_to_find):
        index_to_remove = -1
        # To remove an item, we must first scan the list to find its exact position.

        for index, current_task in enumerate(self.tasks_list):
            if current_task['description'] == description_to_find:
                index_to_remove = index
                break
        
        # If the task was found, we use its position to remove it from the list.

        if index_to_remove != -1:
            self.tasks_list.pop(index_to_remove)
            return True
        return False

    def get_all_tasks(self):
        return self.tasks_list

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the need to find a specific task before performing an action like editing, deleting, or marking it complete. Let n be the total number of tasks in the list. According to the described approach, we must perform a linear search, starting from the first task and checking each one sequentially until the target is found. In the worst-case scenario, such as when the task is the last one or not present, this search requires examining all n tasks. Therefore, the number of operations is directly proportional to n, which simplifies to a time complexity of O(n).

Space Complexity

O(1) – Let N be the total number of tasks stored in the container. This container itself is considered input space, not auxiliary space. To perform any operation like finding, editing, or deleting a task, the process involves iterating through the list using a fixed number of variables, such as a single index or pointer. No additional data structures whose size scales with N are created during these operations. Therefore, the auxiliary space required is constant.

Optimal Solution

Approach

The optimal approach is to design the system from the ground up by first clarifying its purpose and features. We then model the core pieces of information, like the tasks themselves, and define the actions that can be performed on them, ensuring the design is flexible enough to grow over time.

Here's how the algorithm would work step-by-step:

First, clarify the exact features the todo list should have by asking questions. Are we just adding and checking off items, or do we need things like due dates, priorities, or multiple lists for different projects?
Next, identify the main concepts or 'nouns' of the system. The most important one is the 'task' itself, but we should also consider the 'user' who owns the tasks.
For each main concept, describe the information it needs to hold. A task, for instance, must have a description, a status (like 'pending' or 'completed'), and a unique ID. It could also have optional details like a due date.
Then, define the core actions or 'verbs' a user can perform. This includes creating a new task, viewing all their tasks, updating a task (like marking it as done), and deleting a task.
Think about how these concepts relate to each other. We need a way to connect each task to the specific user who created it, ensuring people only see their own items.
Finally, consider how the design can handle more complex features in the future. For example, think about how you might add support for sub-tasks or sharing a list with another person without having to start over.

Code Implementation

class TodoList:
    def __init__(self):
        self.next_task_identifier = 1

        # Using a dictionary for the master record allows for O(1) lookup of any task's details.
        self.master_task_directory = {}

        # Separate collections for statuses prevent searching the entire list to filter tasks.
        self.active_task_id_collection = set()
        self.completed_task_id_collection = set()

    def add_task(self, task_description):
        current_task_identifier = self.next_task_identifier
        self.next_task_identifier += 1

        self.master_task_directory[current_task_identifier] = {
            'description': task_description,
            'status': 'active'
        }

        # Placing the new task's ID directly into the 'active' collection avoids future searches.
        self.active_task_id_collection.add(current_task_identifier)
        return current_task_identifier

    def complete_task(self, task_identifier_to_complete):
        if task_identifier_to_complete in self.active_task_id_collection:
            self.active_task_id_collection.remove(task_identifier_to_complete)
            self.completed_task_id_collection.add(task_identifier_to_complete)
            self.master_task_directory[task_identifier_to_complete]['status'] = 'completed'
            return True
        return False

    def get_active_tasks(self):
        active_tasks = []
        for task_identifier in self.active_task_id_collection:
            active_tasks.append(self.master_task_directory[task_identifier])
        return active_tasks

    def edit_task(self, task_identifier_to_edit, new_task_description):
        if task_identifier_to_edit in self.master_task_directory:
            self.master_task_directory[task_identifier_to_edit]['description'] = new_task_description
            return True
        return False

    def delete_task(self, task_identifier_to_delete):
        if task_identifier_to_delete in self.master_task_directory:
            del self.master_task_directory[task_identifier_to_delete]

            # The identifier must be removed from any status collection it might be in for consistency.
            self.active_task_id_collection.discard(task_identifier_to_delete)
            self.completed_task_id_collection.discard(task_identifier_to_delete)
            return True
        return False

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the operation that scales with the data size, such as viewing all tasks. Assuming a user has 'n' tasks, displaying the entire list requires iterating through each task one by one. The core actions of creating a new task, or updating and deleting a specific task by its unique ID, can be performed in O(1) constant time if we use a hash map for direct access. The cost is therefore driven by the linear scan of all 'n' items for the list-view operation, which results in a complexity of O(n).

Space Complexity

O(N) – The system's primary function is to store the information it manages, particularly the tasks. Let N be the total number of tasks created by all users. The design necessitates data structures, such as lists or hash maps, to hold the N individual task objects, each storing its description, status, and ID. As users add more tasks, the memory required for this central storage grows in direct proportion to N. Consequently, the overall space complexity is determined by the total number of tasks the system must maintain.

Edge Cases

Case	How to Handle
Retrieving todos for a user ID that has no associated todos.	The system should gracefully return an empty list instead of null or an error.
Attempting to delete a todo using a todoId that does not exist.	The operation should complete silently without altering the data structure or throwing an exception.
A single user having a vast number of todos, near the system's maximum capacity.	The chosen data structures must scale efficiently, ensuring operations for this user do not degrade performance for others.
Deleting the very last todo item for a specific user.	Subsequent calls to getTodos for this user must correctly return an empty list, reflecting the new state.
Ensuring insertion order is maintained for a user's todos after intermittent deletions.	The solution must use an order-preserving data structure for each user's todos to guarantee the correct sequence is always returned.
Calling getTodos or deleteTodo on a newly initialized, completely empty TodoList.	These initial calls should be handled correctly, returning an empty list or performing a no-op, respectively.
Interleaved add and delete operations across different users.	The design must ensure strict data isolation between users, preventing one user's actions from corrupting another's todo list.
Calling deleteTodo multiple times consecutively with the same non-existent or already-deleted todoId.	The first deletion attempt on a valid ID succeeds, while all subsequent attempts should be handled as harmless no-ops.

Retrieving todos for a user ID that has no associated todos.

How to Handle:

The system should gracefully return an empty list instead of null or an error.

Attempting to delete a todo using a todoId that does not exist.

How to Handle:

The operation should complete silently without altering the data structure or throwing an exception.

A single user having a vast number of todos, near the system's maximum capacity.

How to Handle:

The chosen data structures must scale efficiently, ensuring operations for this user do not degrade performance for others.

Deleting the very last todo item for a specific user.

How to Handle:

Subsequent calls to getTodos for this user must correctly return an empty list, reflecting the new state.

Ensuring insertion order is maintained for a user's todos after intermittent deletions.

How to Handle:

The solution must use an order-preserving data structure for each user's todos to guarantee the correct sequence is always returned.

Calling getTodos or deleteTodo on a newly initialized, completely empty TodoList.

How to Handle:

These initial calls should be handled correctly, returning an empty list or performing a no-op, respectively.

Interleaved add and delete operations across different users.

How to Handle:

The design must ensure strict data isolation between users, preventing one user's actions from corrupting another's todo list.

Calling deleteTodo multiple times consecutively with the same non-existent or already-deleted todoId.

How to Handle:

The first deletion attempt on a valid ID succeeds, while all subsequent attempts should be handled as harmless no-ops.