Weaving Spells - codepath/compsci_guides GitHub Wiki

TIP102 Unit 7 Session 1 Standard (Click for link to problem statements)

Problem 8: Weaving Spells

A magician can double a spell's power if they merge two incantations together. Given the heads of two linked lists spell_a and spell_b where each node in the lists contains a spell segment, write a recursive function weave_spells() that weaves spells in the pattern:

a1 -> b1 -> a2 -> b2 -> a3 -> b3 -> ...

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Recursion, Linked Lists

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?
  • Q: What is the main task in this problem?
    • A: The task is to weave two linked lists by alternating their nodes using recursion.
  • Q: What should the function return if one of the linked lists is empty?
    • A: The function should return the non-empty list.
HAPPY CASE
Input: 
spell_a = Node('A', Node('C', Node('E')))
spell_b = Node('B', Node('D', Node('F')))
Output: A -> B -> C -> D -> E -> F
Explanation: The nodes from both linked lists are alternated to create the resulting list.

EDGE CASE
Input: spell_a = Node('A'), spell_b = None
Output: A
Explanation: If one list is empty, the other list should be returned as it is.

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 Merging Linked Lists, we want to consider the following approaches:

  • Recursive Weaving: Recursively weave the nodes from the two lists by alternating them and returning the new head of the combined list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • Use recursion to weave the nodes from the two linked lists. If one list is empty, return the other list. Otherwise, weave the current nodes and proceed with the next nodes.

Recursive Approach:

1) Base case: If either `spell_a` or `spell_b` is `None`, return the non-empty list.
2) Weave the current node from `spell_a` with the current node from `spell_b`.
3) Recurse with the next node of `spell_a` and the next node of `spell_b`.
4) Return the head of the new list, starting with the node from `spell_a`.

⚠️ Common Mistakes

  • Not correctly handling the base cases where one or both of the lists are empty.
  • Incorrectly assigning the next pointers, leading to broken links in the resulting list.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def weave_spells(spell_a, spell_b):
    # Base cases
    if not spell_a:
        return spell_b
    if not spell_b:
        return spell_a
    
    # Weave the current nodes
    spell_a.next = weave_spells(spell_b, spell_a.next)
    
    # Return the new head of the list
    return spell_a

# For testing
def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> " if current.next else "\n")
        current = current.next

5: R-eview

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

  • Trace through the weave_spells function with the inputs spell_a = Node('A', Node('C', Node('E'))), spell_b = Node('B', Node('D', Node('F'))). The function should return a linked list with nodes A -> B -> C -> D -> E -> F.
  • Test the function with edge cases where one or both linked lists are empty.

6: E-valuate

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

  • Time Complexity: O(N + M) where N and M are the lengths of the two linked lists. The function processes each node exactly once.
  • Space Complexity: O(N + M) due to the recursion stack. The depth of recursion is proportional to the total number of nodes in both lists.