Amazon Interview Question
Software Engineer in Testsnode *insertAtBegin(node *start, int n)
{
node *temp = (node *)malloc(sizeof(node));
temp->data = n;
temp->next = start;
return temp;
}
node *reverseList (node *start)
{
node *prev = NULL;
node *temp;
while (start)
{
temp = start->next;
start->next = prev;
prev = start;
start = temp;
}
return prev;
}
node *addNums(node *num1, node *num2)
{
num1 = reverseList(num1);
num2 = reverseList(num2);
node *tmp1 = num1, *tmp2 = num2;
node *num3 = NULL;
int carry = 0, sum;
while (num1 && num2)
{
sum = num1->data + num2->data + carry;
num3 = insertAtBegin(num3,sum%10);
carry = sum/10;
}
num1 = num1 ? num1 : num2;
while (num1)
{
sum = num1->data + carry;
num3 = insertAtBegin(num3,sum%10);
carry = sum/10;
}
if (carry)
num3 = insertAtBegin(num3,carry);
num1 = reverseList(tmp1);
num2 = reverseList(tmp2);
return num3;
}
Simple Algorithm:
Assuming L1 and L2 are given and sum is stored in L3
1. Reverse L1;
2. Reverse L2;
3. put=0;keep=0;
4. While (L1 or L2)
sum=L1.data + L2.data + keep;
if(sum >10) then put=sum-10; keep=1
else put=sum; keep=0
L3.insert(put)
L1.moveForward
L2.moveForward
End While;
if(keep!=0) then L3.insert(keep)
//take care of condition when either L1 or L2 becomes empty
5. L3.reverse
6. return L3
1). I'm taking that the numbers are represented as below:
- Hari October 16, 2009123: NULL <--- 1 <--- 2 <--- 3
789: NULL <--- 7 <--- 8 <--- 9
2). For the resultant list, I'm re-using the nodes of the first list.
3). The nodes of the second list are freed.
<snip>
cry = 0;
tmp = l2->next;
while (l1->next && l2->next) {
l1 = l1->next; // Header assumed.
l2 = tmp;
tmp = l2->next;
dig = (l1->val + l2->val + cry) % 10;
rem = (l1->val + l2->val + cry) / 10;
l1->val = dig;
cry = rem;
free(l2); // deallocating each node as it's traversed.
}
if (! l1->next) { //l2 has more digits
l1->next = l2->next;
l2->val += cry;
} else { //l1 has more digits than l2.
l2->next = l1;
l1->val += cry;
}
</snip>
Please correct, if there are any mistakes.
Thanks & Regards,
Hari.