Meta Data Engineer Interview Experience — TaskManager Sorting Problem Extended to Multi-Level Parent/Child Tasks

A very "engineering-style" interview question: implement a TaskManager class that filters, de-duplicates, sorts and prints tasks according to rules, and once the basic version is done, extend it to multi-level parent/child tasks. The question doesn't test long, fancy algorithms. It tests requirement clarification, choice of data structures, multi-key sorting and tree traversal.

Problem overview

Implement a TaskManager class that takes a set of existing tasks as initialization data and provides a print_prioritized_tasks method, which outputs tasks according to the given filtering, de-duplication and sorting rules. After the basic version, extend it to support multi-level parent/child task relationships.

Each task has 8 fields: task id, task description, whether it is completed, due date (can be empty), parent task id (can be empty), assignee (can be empty), whether it is high priority, and creation timestamp.

Part 1: basic task sorting

Rules

Filtering and de-duplication

• Keep only tasks that are not completed and have no assignee;
• Use "description + due date" as the de-duplication key;
• For duplicate tasks, keep only the first record that passes the filter.

Sorting

• Tasks with a due date come first, sorted by due date ascending;
• If due dates are equal, high-priority tasks come first;
• If priority is also equal, the task created earlier comes first;
• Tasks without a due date come after all tasks that have a due date.

Output format

One line per task: "Task ID" plus the id, "Description" plus the description. If the task has a parent, append "parent: <parent task description>" at the end.

Clarifying questions

After getting the problem I didn't start coding right away. I first confirmed five things:

1. Keep the first or the last of the duplicate tasks? The interviewer said: keep the first one;
2. Do tasks without a due date always come after tasks with a due date? Yes;
3. If a task has a parent task id but the parent doesn't exist, should I just print the task without the parent suffix? I can assume the parent task id is always valid;
4. Can I just output to the console with print()? Yes;
5. Can I assume all task ids are unique and all due dates are in YYYY-MM-DD format? Yes.

These five questions are all concrete, and each one maps to a branch or an assumption in the code. If you clarify well, you won't have to redo work later because of a misunderstanding. The "all due dates are YYYY-MM-DD" one was especially useful: comparing strings in that format is the same as comparing the dates, so no extra parsing is needed.

Approach

1. Build a task index: at initialization, build a dictionary keyed by task id so a parent task can be looked up by its parent id;
2. Filter: drop tasks that are completed or already assigned;
3. De-duplicate: use "description + due date" as the key, keeping the first record that passes the filter;
4. Sort: use a tuple sort key that compares, in order, "is the due date empty", the due date, the priority, and the creation time;
5. Print: walk through the sorted tasks, format the output as required, and append the parent's description when there is a parent.

The "tuple sort key" is the core trick of this problem: write the four conditions into one tuple from highest to lowest priority and let the language's built-in sort compare them in order. "No due date goes last" is expressed by the first element, "is the due date empty"; "high priority goes first" requires negating the boolean, because in ascending order false comes before true.

Complexity

• Time complexity O(n log n), mainly from the sort; filtering, de-duplication and building the task index are all expected O(n);
• Space complexity O(n), for the task index, the de-duplication set and the processed task list.

Part 2: multi-level parent/child task sorting

Extension requirements

• Support multi-level parent/child task relationships;
• A child task normally comes right after its parent task;
• If a child task has a due date and the parent does not, the child should come before the parent;
• If a child task's due date is earlier than the parent's, the child should also come before the parent;
• Among multiple child tasks, keep following the original sorting rules;
• The same rules apply recursively to deeper levels.

The essence of this part: turn the "flat task list" into a forest, and at each parent task arrange its child tasks using the same set of rules.

Approach

1. Global task dictionary: look up any task quickly by its id;
2. Adjacency list: record the direct children of each parent task;
3. Recursive DFS: walk the task hierarchy recursively, applying the same sorting logic at each parent task;
4. Grouping the children: separate the child tasks that need to come before the parent from the rest;
5. Output order: handle the children that need to come earlier first, then output the parent task, and finally handle the remaining children;
6. Avoiding duplicates: use a visited set to record the task ids already output, so that a child task output early is not output again.

The output order "leading children, then parent, then trailing children" is the key to the whole problem. It is effectively a kind of "custom in-order traversal".

Interviewer follow-up

The interviewer's gist was to confirm: so you would have a global task dictionary or some other structure to store the tasks, and when outputting a task you check its child tasks, right?

My answer was: yes. I use a global task dictionary to store all tasks, an adjacency list to record each parent's children, and then process with a recursive DFS. Before outputting a task, I first check whether any of its children need to come before it; to avoid outputting anything twice, I keep a visited set of the tasks already handled.

I think this answer was solid: first confirm the interviewer's understanding, then say all three things (dictionary, adjacency list, visited set) in one go, without going in circles.

Interview focus review

• Object-oriented design: sensibly split the work into initialization, task processing, sorting and printing methods;
• Choice of data structures: a dictionary for id lookup, a set for de-duplication and visit tracking;
• Multi-key sorting: use a tuple sort key to implement several sorting conditions;
• Tree traversal: use an adjacency list and DFS to handle multi-level parent/child relationships;
• Edge cases: empty due dates, duplicate tasks, due-date conflicts between parent and child, and duplicate output;
• Complexity analysis: explain the cost of sorting, and the space needed by the index, the sets and the recursive traversal.

Things I thought of after the interview

• Part 2 leaves some things open: for example, what to do when the parent task is filtered out (completed or assigned) but the child task still qualifies. One simple convention: only build the hierarchy among the tasks that survive filtering and de-duplication, and treat a task whose parent is not among them as a root. In the interview you can raise this assumption yourself and have the interviewer confirm it.
• Circular dependencies: if the data has A as the parent of B and B as the parent of A, the recursion loops forever. The visited set prevents duplicate output, but if the data itself is invalid it should raise an error.
• Recursion depth: if the hierarchy is extremely deep the recursion can overflow the stack; you can mention switching to an iterative version with an explicit stack.
• Code structure: write the sort key as its own function, so the global sort in Part 1 and the sibling sort in Part 2 can both reuse it, which keeps the changes for the extension minimal.

Takeaways

1. Make clarifying questions concrete and tied to a code branch. Which duplicate to keep, where empty dates go, what to do when the parent is missing: each question lands on one line of code.
2. Use a tuple for multi-key sorting. Priorities go into one tuple from highest to lowest, and be able to explain the two small tricks, "empties go last" and "negate the boolean".
3. For an extension question, get the base version solid first. The filtering, de-duplication and sorting logic from Part 1 should be fully reusable; Part 2 just adds a layer of tree traversal on top of the output order.
4. Be able to explain "leading children, then parent, then trailing children" clearly. It is the one sentence that explains the recursive structure.
5. Propose assumptions proactively. Where the problem leaves gaps, state your own convention first; it earns more points than silently picking one.