Puzzling it Out - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 2 Standard (Click for link to problem statements)

Problem Highlights

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

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 does the problem ask for?
    • The problem asks to merge two sorted linked lists into one sorted linked list.
  • What should be returned?
    • The function should return the head of the merged sorted linked list.
HAPPY CASE
Input: known_timeline = Node(1, Node(2, Node(4)))
       witness_timeline = Node(1, Node(3, Node(4)))
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Explanation: The two linked lists are merged into a single sorted linked list.

EDGE CASE
Input: known_timeline = Node(1, Node(2, Node(4)))
       witness_timeline = None
Output: 1 -> 2 -> 4
Explanation: The witness timeline is empty, so the merged list is just the known timeline.

EDGE CASE
Input: known_timeline = None
       witness_timeline = Node(2, Node(3, Node(4)))
Output: 2 -> 3 -> 4
Explanation: The known timeline is empty, so the merged list is just the witness timeline.

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

  • Two-Pointer Technique: Use two pointers to traverse the linked lists and merge them into one sorted list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use two pointers, one for each linked list, to traverse the lists and build a new merged linked list in sorted order.

1) Initialize a temporary head node to help build the merged list.
2) Initialize a pointer `current` to the temporary head node.
3) Initialize two pointers `p1` and `p2` to the heads of the known and witness timelines, respectively.
4) Traverse both lists:
    a) Compare the values at `p1` and `p2`.
    b) Attach the node with the smaller value to `current` and move the pointer of that list forward.
    c) Move `current` forward.
5) Once one list is exhausted, attach the remaining nodes of the other list to the merged list.
6) Return the node next to the temporary head (the head of the merged list).

⚠️ Common Mistakes

  • Forgetting to handle cases where one or both input lists are empty.
  • Incorrectly managing pointers, leading to a cycle in the merged list or loss of nodes.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
    
# Function to merge two sorted linked lists
def merge_timelines(known_timeline, witness_timeline):
    temp_head = Node(0)  # Temporary head for the merged list
    current = temp_head  # Pointer to build the new list
    
    # Pointers to traverse both lists
    p1 = known_timeline
    p2 = witness_timeline
    
    while p1 and p2:
        if p1.value <= p2.value:
            current.next = p1
            p1 = p1.next
        else:
            current.next = p2
            p2 = p2.next
        current = current.next
    
    # Attach remaining nodes (one of these will be None)
    if p1:
        current.next = p1
    else:
        current.next = p2
    
    return temp_head.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: Use the provided known_timeline and witness_timeline linked lists to verify that the function correctly merges the lists.

6: E-valuate

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

Assume N and M represent the number of nodes in the known and witness timelines, respectively.

  • Time Complexity: O(N + M) because each node from both linked lists is visited exactly once.
  • Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers.