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?
HAPPY CASE
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]
EDGE CASE
Input: l1 = [0], l2 = [0]
Output: [0]
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 Lists problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Obtain the length of both linked list. Recursively iterate through both lists and sum the values of the nodes and remainder from the previous addition for each node of equal length.
1) Get the length of the linked lists
2) Add the linked lists recursively
a) Basecase: End of List -> Return None and carry value of 0
b) Get Current Sum and Current Carry Value to recursively pass back to calling function
i) Get Current Sum by adding value at l1, l2, and carry value.
1. If len1 > len2, then recursively call l1.next, to get next head node and carry value, as this signifies adding l1 value and 0
2. If len2 > len1, then recursively call l2.next, to get next head node and carry value, as this signifies adding l2 value and 0
3. If len1 == len2, then recursively call l1.next and l2.next, to get next head node and carry value, as this signifies adding both values
ii) Get Current Carry Value by floor divide Current Sum
iii) Get Current Sum Digit by module Current Sum
c) Return Current Node with Current Sum Digit as value and previous head node as next node AND Current Carry Value
3) After recusive call, if there is carry over value, set as head node
4) Return the head node⚠️ Common Mistakes
Implement the code to solve the algorithm.
Iterative
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# Create function to Reverse Linked List
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
prev, curr = None, head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
# Reverse Linked List
r1 = reverseList(l1)
r2 = reverseList(l2)
# Add the two numbers in reverse
currVal = 0
carry = 0
tempHead = ListNode()
while r1 or r2:
if r1:
currVal += r1.val
r1 = r1.next
if r2:
currVal += r2.val
r2 = r2.next
tempHead.val = currVal % 10
carry = currVal // 10
prevNode = ListNode(carry)
prevNode.next = tempHead
tempHead = prevNode
currVal = carry
return tempHead.next if carry == 0 else tempHeadclass Solution {
// Create function to Reverse Linked List
public ListNode reverseList(ListNode head) {
ListNode prev = null, temp;
while (head != null) {
// Keep the next node
temp = head.next;
// Reverse the link
head.next = prev;
// Update the previous node and the current node.
prev = head;
head = temp;
}
return prev;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Reverse Linked List
ListNode r1 = reverseList(l1);
ListNode r2 = reverseList(l2);
// Add the two numbers in reverse
int currVal = 0, carry = 0;
ListNode tempHead = new ListNode();
while (r1 != null || r2 != null) {
if (r1 != null) currVal += r1.val;
if (r2 != null) currVal += r2.val;
tempHead.val = currVal % 10;
carry = currVal / 10;
ListNode prevNode = new ListNode(carry);
prevNode.next = tempHead;
tempHead = prevNode;
currVal = carry;
r1 = r1 != null ? r1.next : null;
r2 = r2 != null ? r2.next : null;
}
// Return the linked list with or without the starting 0
return carry == 0 ? tempHead.next: tempHead;
}
}Recursive
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# Get the length of the linked lists
len1, len2 = self._getLength(l1), self._getLength(l2)
# Add the linked lists recursively
head, carry = self._addRecursively(l1, len1, l2, len2)
# After recusive call, if there is carry over value, set as head node
if carry:
head = ListNode(carry, head)
# Return the head node
return head
# Add the linked lists recursively
def _addRecursively(self, l1: Optional[ListNode], len1: int, l2: Optional[ListNode], len2: int) -> (Optional[ListNode], int):
# Basecase: Return None and carry value of 0
if not l1 and not l2:
return (None, 0)
# Get Current Sum and Current Carry Value to recursively pass back to calling function
current_sum = 0
current_carry = 0
# Get Current Sum by adding value at l1, l2, and carry value.
if len1 > len2:
# If len1 > len2, then recursively call l1.next, to get next head node and carry value, as this signifies adding l1 value and 0
head, carry = self._addRecursively(l1.next, len1 - 1, l2, len2)
current_sum = l1.val + 0 + carry
elif len1 < len2:
# If len2 > len1, then recursively call l2.next, to get next head node and carry value, as this signifies adding l2 value and 0
head, carry = self._addRecursively(l1, len1, l2.next, len2 - 1)
current_sum = 0 + l2.val + carry
else:
# If len1 == len2, then recursively call l1.next and l2.next, to get next head node and carry value, as this signifies adding both values
head, carry = self._addRecursively(l1.next, len1 - 1, l2.next, len2 - 1)
current_sum = l1.val + l2.val + carry
# Get Current Carry Value by floor divide Current Sum
current_carry = current_sum // 10
# Get Current Sum Digit by module Current Sum
current_sum_digit = current_sum % 10
# Return Current Node with Current Sum Digit as value and previous head node as next node AND Current Carry Value
return (ListNode(current_sum_digit, head), current_carry)
def _getLength(self, head: ListNode) -> int:
result = 0
curr = head
while curr:
curr = curr.next
result += 1
return result/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Get the length of the linked lists
int len1 = getLength(l1);
int len2 = getLength(l2);
//Making sure l1 is always greater than l2
if(len2 > len1) {
ListNode temp = l1;
l1 = l2;
l2 = temp;
int t = len1;
len1 = len2;
len2 = t;
}
// Add the linked lists recursively
int rem = logic(l1, l2, len1, len2, 0, 0);
// After recusive call, if there is carry over value, set as head node
if(rem != 0) {
return new ListNode(rem, l1);
} else {
// Return the head node
return l1;
}
}
//l1 and l2 are the list length respectively, s1 and s2 are the current index in respect to l1 and l2
public int logic(ListNode l1, ListNode l2, int len1, int len2, int s1, int s2) {
// Basecase: Return None and carry value of 0
if(l1 == null) return 0;
int diff = len1 - len2;
// Get Current Sum and Current Carry Value to recursively pass back to calling function
if(diff != 0 && s2 < diff) {
//case where l2 is smaller than l1, hence we need to skip l2 pointer incrementation
int rem = logic(l1.next, l2, len1, len2, s1+1, s2+1);
int sum = l1.val + rem;
l1.val = sum%10;
return sum/10;
} else {
int rem = logic(l1.next, l2.next, len1, len2, s1+1, s2+1);
int sum = l1.val + l2.val + rem;
l1.val = sum%10;
return sum/10;
}
}
//Utility method to get the length of the list
public int getLength(ListNode head) {
int length = 0;
while(head != null) {
length++;
head = head.next;
}
return length;
}
}Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N represents the number of nodes in the linked list 1. M represents the number of nodes in the linked list 2.
O(N or M) because we need to make N or M recursive calls to add the all digits. Constant Time. O(1) not counting the memory stack, because the maximum number of recursive calls we need to store in the memory stack is based on O(N or M)
