Super Sandwich - codepath/compsci_guides GitHub Wiki

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

Problem 4: Super Sandwich

A regular at the deli has requested a new order made by merging two different sandwiches on the menu together. Given the heads of two linked lists sandwich_a and sandwich_b where each node in the lists contains a sandwich ingredient, write a recursive function merge_orders() that merges the two sandwiches together 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 merge two linked lists by alternating nodes from sandwich_a and sandwich_b 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: 
sandwich_a = Node('Bacon', Node('Lettuce', Node('Tomato')))
sandwich_b = Node('Turkey', Node('Cheese', Node('Mayo')))
Output: Bacon -> Turkey -> Lettuce -> Cheese -> Tomato -> Mayo
Explanation: The nodes from both linked lists are alternated to create the resulting list.

EDGE CASE
Input: sandwich_a = Node('Bacon'), sandwich_b = None
Output: Bacon
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 merge 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 `sandwich_a` or `sandwich_b` is `None`, return the non-empty list.
2) Weave the current node from `sandwich_a` with the current node from `sandwich_b`.
3) Recurse with the next node of `sandwich_a` and the next node of `sandwich_b`.
4) Return the head of the new list, starting with the node from `sandwich_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 merge_orders(sandwich_a, sandwich_b):
    # Base case: if one of the lists is empty, return the other
    if not sandwich_a:
        return sandwich_b
    if not sandwich_b:
        return sandwich_a
    
    # Recursive case: merge first nodes of both lists and recurse
    next_a = sandwich_a.next
    next_b = sandwich_b.next
    
    sandwich_a.next = sandwich_b
    sandwich_b.next = merge_orders(next_a, next_b)
    
    return sandwich_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 merge_orders function with the inputs sandwich_a = Node('Bacon', Node('Lettuce', Node('Tomato'))), sandwich_b = Node('Turkey', Node('Cheese', Node('Mayo'))). The function should return a linked list with nodes Bacon -> Turkey -> Lettuce -> Cheese -> Tomato -> Mayo.
  • 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:

  • 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.

Discussion:

  • This recursive approach effectively merges the two linked lists by alternating their nodes, maintaining the original order within each list.
  • While this solution is straightforward and leverages recursion, an iterative approach could be explored to avoid the additional space complexity caused by the recursion stack.