TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
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
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:
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
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)
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
monthly_listeners1
and monthly_listeners2
linked lists to verify that the function correctly doubles the integer values represented by the linked lists.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the length of the linked list.
O(N)
because we traverse the entire linked list once.O(1)
because the algorithm uses a constant amount of extra space for pointers and carry.