Adding Up the Evidence - 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, Addition, Carry Management

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 add two numbers represented by linked lists where each node contains a single digit in reverse order. The result should also be represented as a linked list in reverse order.
  • What should be returned?
    • The function should return the head of a linked list representing the sum of the two numbers.
HAPPY CASE
Input: head_a = Node(2, Node(4, Node(3)))  # 342
       head_b = Node(5, Node(6, Node(4)))  # 465
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807. The result is represented as 7 -> 0 -> 8.

EDGE CASE
Input: head_a = Node(9, Node(9, Node(9)))  # 999
       head_b = Node(1)                    # 1
Output: 0 -> 0 -> 0 -> 1
Explanation: 999 + 1 = 1000. The result is represented as 0 -> 0 -> 0 -> 1.

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 Addition and Carry Management, we want to consider the following approaches:

  • Traversal: Traverse both linked lists simultaneously, adding corresponding digits and managing carry-over.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse both linked lists, adding the corresponding digits along with any carry-over from the previous step. The sum will be stored in a new linked list.

1) Initialize a temporary head node to simplify edge cases.
2) Initialize a variable `carry` to 0.
3) Traverse both linked lists simultaneously:
    a) Add the values of the current nodes and the carry.
    b) Create a new node with the digit value of the sum % 10.
    c) Update the carry to sum // 10.
    d) Move to the next nodes in both lists.
4) If any carry remains after traversal, add a new node with the carry value.
5) Return the next node of the temporary head (skipping the initial dummy node).

⚠️ Common Mistakes

  • Forgetting to handle cases where the carry remains after processing all nodes.
  • Not correctly managing the addition when one list is longer than the other.

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 add two numbers represented as linked lists
def add_two_numbers(head_a, head_b):
    temp_head = Node(0)  # Temporary head node for the result list
    current = temp_head
    carry = 0

    while head_a or head_b or carry:
        sum_value = carry
        if head_a:
            sum_value += head_a.value
            head_a = head_a.next
        if head_b:
            sum_value += head_b.value
            head_b = head_b.next

        carry = sum_value // 10
        current.next = Node(sum_value % 10)
        current = current.next

    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 head_a and head_b linked lists to verify that the function correctly adds the two numbers.

6: E-valuate

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

Assume N represents the number of nodes in the longer of the two linked lists.

  • Time Complexity: O(N) because each node is visited exactly once.
  • Space Complexity: O(N) because a new linked list is created to store the result.