Double Listening Count - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Linked Lists, Arithmetic Operations, Carry Forward

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What does the problem ask for?
  • A: The problem asks to double the integer value represented by a linked list and return the head of the new list representing the doubled value.
• Q: What should be returned?
  • A: The function should return the head of the modified linked list after doubling the integer value.

HAPPY CASE
Input: 
    - monthly_listeners1 = Node(1, Node(8, Node(9))) # 189
    - monthly_listeners2 = Node(9, Node(9, Node(9))) # 999
Output: 
    - 3 -> 7 -> 8
    - 1 -> 9 -> 9 -> 8
Explanation: 
    - 189 * 2 = 378
    - 999 * 2 = 1998

EDGE CASE
Input: 
    - monthly_listeners = Node(5, Node(0, Node(0))) # 500
Output: 
    - 1 -> 0 -> 0 -> 0
Explanation: 
    - 500 * 2 = 1000

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 Arithmetic Operations and Carry Handling, we want to consider the following approaches:

• Traversal with Carry Handling: Traverse the linked list, double each node's value, and manage any carry that results from the doubling operation.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list, double each node's value, handle any carry that results from the doubling, and create new nodes if there is a carry at the end of the list.

1) Reverse the linked list to start from the least significant digit (the last `node`).
2) Initialize a pointer `current` to the `head` of the reversed list and a variable `carry` to `0`.
3) Traverse the reversed linked list:
   - Double the value of the `current` node and add any `carry` from the previous operation.
   - Update the `node`'s value to be `doubled_value % 10`.
   - Calculate the new `carry` as `doubled_value // 10`.
4) If there is a `carry` left after traversing all nodes, create a new `node` with the `carry` value at the end of the list.
5) Reverse the list again to restore its original order.
6) Return the `head` of the modified linked list.

⚠️ Common Mistakes

• Forgetting to handle cases where the carry is greater than 0 after the last node.
• Incorrectly managing pointers, leading to loss of nodes or incorrect traversal.

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 double_listeners(monthly_listeners):
    def reverse_list(head):
        prev = None
        current = head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        return prev

    head = reverse_list(monthly_listeners)
    
    current = head
    carry = 0
    while current:
        doubled_value = current.value * 2 + carry
        current.value = doubled_value % 10  # Update the current node's value
        carry = doubled_value // 10  # Carry over the remaining part of the doubled value
        if current.next is None and carry > 0:
            current.next = Node(carry)  # If it's the last node and there's a carry, add a new node
            break
        current = current.next

    return reverse_list(head)

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 monthly_listeners1 and monthly_listeners2 linked lists to verify that the function correctly doubles the integer values represented by the linked lists.

6: E-valuate

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

Assume N represents the length of the linked list.

• Time Complexity: O(N) because we traverse the entire linked list once.
• Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers and carry.