TIP102 Unit 7 Session 1 Advanced (Click for link to problem statements)
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 -> ...
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?
sandwich_a and sandwich_b using recursion.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.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:
Plan the solution with appropriate visualizations and pseudocode.
General Idea:
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
next pointers, leading to broken links in the resulting list.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.nextReview the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
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.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(N + M) where N and M are the lengths of the two linked lists. The function processes each node exactly once.O(N + M) due to the recursion stack. The depth of recursion is proportional to the total number of nodes in both lists.