Creating Cookie Orders from Descriptions - codepath/compsci_guides GitHub Wiki

TIP102 Unit 9 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-25 mins
🛠️ Topics: Trees, Tree Construction, Parent-Child Relationships

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

What is the structure of the tree?
- The tree is a binary tree where each node represents a flavor of cookie ordered by customers.
What operation needs to be performed?
- The function needs to construct a binary tree based on the given parent-child relationships.
What should be returned?
- The function should return the root of the constructed binary tree.

HAPPY CASE
Input: 
    descriptions1 = [
        ["Chocolate Chip", "Peanut Butter", 1],
        ["Chocolate Chip", "Oatmeal Raisin", 0],
        ["Peanut Butter", "Sugar", 1]
    ]
Output: 
    ['Chocolate Chip', 'Peanut Butter', 'Oatmeal Raisin', 'Sugar']
Explanation: 
    The tree structure:
          Chocolate Chip
         /              \
    Peanut Butter     Oatmeal Raisin
        /
     Sugar

EDGE CASE
Input: 
    descriptions2 = [
        ["Ginger Snap", "Snickerdoodle", 0],
        ["Ginger Snap", "Shortbread", 1]
    ]
Output: 
    ['Ginger Snap', 'Shortbread', 'Snickerdoodle']
Explanation: 
    The tree structure:
          Ginger Snap
         /           \
    Shortbread   Snickerdoodle

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Tree Construction problems, we want to consider the following approaches:

Hash Maps: Use a hash map to store nodes by their flavor for easy access and to build parent-child relationships.
Set Operations: Use a set to keep track of all child nodes to identify the root node (which will not be a child of any other node).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

Use a hash map to create and store nodes based on the parent-child relationships given in the descriptions.
Use a set to track all child nodes, and finally, find the root node by identifying the node that is not present in the set of child nodes.

1) Initialize a dictionary `nodes` to store TreeNode objects by their flavor.
2) Initialize a set `child_set` to keep track of all child nodes.
3) Iterate over each `description` in `descriptions`:
    - If `parent` is not in `nodes`, create a new TreeNode for `parent` and add it to `nodes`.
    - If `child` is not in `nodes`, create a new TreeNode for `child` and add it to `nodes`.
    - Add `child` to `child_set`.
    - If `is_left == 1`, set `child` as the left child of `parent`.
    - If `is_left == 0`, set `child` as the right child of `parent`.
4) Identify the root node by finding the node in `nodes` that is not in `child_set`.
5) Return the root node.

⚠️ Common Mistakes

Forgetting to account for all possible nodes when determining the root node.
Misplacing the left and right child assignments.

4: I-mplement

Implement the code to solve the algorithm.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_cookie_tree(descriptions):
    nodes = {}  # To store nodes by their flavor
    child_set = set()  # To keep track of all child nodes

    # Step 1: Create nodes and establish parent-child relationships
    for parent, child, is_left in descriptions:
        if parent not in nodes:
            nodes[parent] = TreeNode(parent)
        if child not in nodes:
            nodes[child] = TreeNode(child)
        
        child_set.add(child)
        
        if is_left == 1:
            nodes[parent].left = nodes[child]
        else:
            nodes[parent].right = nodes[child]

    # Step 2: Find the root (the one node not in the child_set)
    root = None
    for parent in nodes:
        if parent not in child_set:
            root = nodes[parent]
            break

    return root

# Example Usage:
descriptions1 = [
    ["Chocolate Chip", "Peanut Butter", 1],
    ["Chocolate Chip", "Oatmeal Raisin", 0],
    ["Peanut Butter", "Sugar", 1]
]
descriptions2 = [
    ["Ginger Snap", "Snickerdoodle", 0],
    ["Ginger Snap", "Shortbread", 1]
]

print_tree(build_cookie_tree(descriptions1))
print_tree(build_cookie_tree(descriptions2))

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

- Example 1:
    - Input: 
        `descriptions1 = [
            ["Chocolate Chip", "Peanut Butter", 1],
            ["Chocolate Chip", "Oatmeal Raisin", 0],
            ["Peanut Butter", "Sugar", 1]
        ]`
    - Execution: 
        - Construct the tree by creating nodes and linking them according to the descriptions.
        - Identify "Chocolate Chip" as the root node.
    - Output: 
        ['Chocolate Chip', 'Peanut Butter', 'Oatmeal Raisin', 'Sugar']

- Example 2:
    - Input: 
        `descriptions2 = [
            ["Ginger Snap", "Snickerdoodle", 0],
            ["Ginger Snap", "Shortbread", 1]
        ]`
    - Execution: 
        - Construct the tree by creating nodes and linking them according to the descriptions.
        - Identify "Ginger Snap" as the root node.
    - Output: 
        ['Ginger Snap', 'Shortbread', 'Snickerdoodle']

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

Time Complexity: O(N) where N is the number of descriptions.
- Explanation: We iterate over the descriptions once to construct the tree, and the operations performed within each iteration (creating nodes, setting children) take constant time.

Space Complexity:

Space Complexity: O(N) where N is the number of nodes in the tree.
- Explanation: We store up to N nodes in the nodes dictionary and N children in the child_set.