The Pensieve's Memories

JCSU Unit 10 Problem Set 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Linked Lists, Merging, Two Pointers

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 goal of the problem?
  • Merge two sorted linked lists into a single sorted linked list by splicing nodes together.
• Are there constraints on input?
  • Input linked lists are sorted in ascending order, and the merged list must also be sorted.

HAPPY CASE Input: memory_stream1 = 2 -> 4 -> 6 memory_stream2 = 1 -> 3 -> 5 Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 Explanation: The nodes from both memory streams are merged in ascending order.

EDGE CASE Input: memory_stream1 = None memory_stream2 = None Output: None Explanation: Both input lists are empty, so the merged list is also empty.

EDGE CASE Input: memory_stream1 = None memory_stream2 = 1 -> 3 -> 5 Output: 1 -> 3 -> 5 Explanation: One input list is empty, so the result is the non-empty list.

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 sorted linked lists, we want to consider the following approaches:

• Two Pointers: Use two pointers to traverse both lists and build the merged list in sorted order.
• Recursive Merging (Alternative): Use recursion to merge the lists (less space-efficient due to stack calls).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Use two pointers to traverse both linked lists. At each step, attach the smaller node to the merged list and move the respective pointer forward. At the end, attach any remaining nodes from the non-exhausted list.

Steps:

1. Create a dummy node to act as the head of the merged list.
2. Initialize a pointer current to build the merged list starting from the dummy node.
3. Traverse both input lists (memory_stream1 and memory_stream2) using a while loop:
   • Compare the current nodes from both lists.
   • Attach the smaller node to current.next and move the pointer in the respective list.
   • Move current forward in the merged list.
4. After the loop, attach any remaining nodes from either list to the merged list.
5. Return dummy.next, skipping the dummy node.

4: I-mplement

Implement the code to solve the algorithm.

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

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

def merge_memories(memory_stream1, memory_stream2):
    # Create a dummy node to act as the head of the merged list
    dummy = Node(0)
    current = dummy  # Pointer to build the merged list

    # Traverse both input lists and merge them in sorted order
    while memory_stream1 and memory_stream2:
        if memory_stream1.value <= memory_stream2.value:
            current.next = memory_stream1  # Attach the smaller node to the merged list
            memory_stream1 = memory_stream1.next  # Move to the next node in memory_stream1
        else:
            current.next = memory_stream2  # Attach the smaller node to the merged list
            memory_stream2 = memory_stream2.next  # Move to the next node in memory_stream2
        current = current.next  # Move the pointer in the merged list

    # Attach any remaining nodes from either list
    if memory_stream1:
        current.next = memory_stream1
    if memory_stream2:
        current.next = memory_stream2

    # Return the head of the merged list, skipping the dummy node
    return dummy.next

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: memory_stream1 = 2 -> 4 -> 6, memory_stream2 = 1 -> 3 -> 5
• Expected Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6
• Observed Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Example 2:

• Input: memory_stream1 = None, memory_stream2 = None
• Expected Output: None
• Observed Output: None

Example 3:

• Input: memory_stream1 = None, memory_stream2 = 1 -> 3 -> 5
• Expected Output: 1 -> 3 -> 5
• Observed Output: 1 -> 3 -> 5

6: E-valuate

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

Assume n is the length of memory_stream1 and m is the length of memory_stream2.

• Time Complexity: O(n + m) because we traverse both lists fully once.
• Space Complexity: O(1) additional space because we rearrange the nodes in-place without creating new ones.