Microsoft Interview Question
Software Engineer in TestsCountry: -
static void sumList(Node head1, Node head2, Node result) {
if (head1 == null || head2 == null) {
return;
}
sumList(head1.next, head2.next, result.next);
int carry = 0;
Node next = result.next;
if (next != null && next.data > 10) {
carry = next.data / 10;
next.data = next.data % 10;
}
result.data = head1.data + head2.data + carry;
}
I guess your code will seg fault @ sumList(head1.next, head2.next, result.next); because your result is already NULL and your are traversing to its next ptr. The following code is only for two list of same sizes. Any concerns let me know.
struct node {
int data;
struct node *next;
};
void sumlist (struct node *list1, struct node *list2, struct node **result) {
if (list1 == NULL && list2 == NULL) {
*result = NULL;
return;
}
sumlist (list1->next, list2->next, result);
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if ( *result != NULL ) {
if (*result->data >= 10) {
*result->data = *result->data - 10;
newnode->data = 1;
}
}
newnode->data = newnode->data + list1->data + list2->data;
newnode->next = *result;
*result = newnode;
}
I understand above code wont work in all the cases. Regarding Seg Fault result is the head node of result linked list which has been already created with input.
You see I never created any node
I'm not quite convinced that your code will work properly in all cases when we have two linked lists with the same length, what the input was 10->10->10 and 0->0->1. This will result 11->1->1 but I'm not sure that this is the correct answer do you??
I don't think above code wil work in case list are of varied length.
I suggest, the simplest way wil be to reverse both linked list, add them to get our sum list, and then reverse all three list to get the original and our answer.
We can do this recursively or by using stack. I choose the latter. I am using a Stack of Integers. The following code will take care of the case where two lists are unequal length.
1. Start putting the integer value of each node of the bigger list on stack until the length of two lists become equal.
2. Start adding the values of data from two lists. At this point do not care about carry and just add them and push onto the stack.
3. Start popping values out of stack and putting them in newly created linked list node. You need to adjust the values by doing sum%10 and carry = sum/10. Use this carry for the next popped out entry. Every node that you create, put it in the front of the list.
NOTE: We might be able to get rid of the stack if we just add the two list and put them in a third list. Then adjust the third list for carry propagation and in the end reverse it. In this case time=O(n) auxiliary space O(1)
But even the stack approach should not be worse than the recursive way.
Here is a code to get you started:
package linkedlist;
import java.util.Stack;
public class SumTwoList {
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// traverse through the list to find the size
private int size(Node head) {
Node temp = head;
int len = 0;
while (temp != null) {
len++;
temp = temp.next;
}
return len;
}
public Node addLists(Node head1, Node head2) {
// if either of the lists are empty then take appropriate action
if (head1 == null && head2 == null) {
return null;
} else if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
Node result = null;
Stack<Integer> s = new Stack<Integer>();
int l1 = size(head1);
int l2 = size(head2);
int len = 0;
int i;
// start pushing the bigger list items on the stack
if (l1 > l2) {
len = l2;
for (i = 0; i < l1 - l2; i++) {
s.push(head1.data);
head1 = head1.next;
}
} else if (l1 < l2) {
len = l1;
for (i = 0; i < l2 - l1; i++) {
s.push(head2.data);
head2 = head2.next;
}
}
// Now both lists are same length push the sum on the stack
for (i = 0; i < len; i++) {
s.push(head1.data + head2.data);
}
int sum = 0, carry = 0;
// start popping the sum and adjusting the sum carry values and put it in a new list
while (s.isEmpty() == false) {
sum = s.pop() + carry;
Node n = new Node(sum % 10);
n.next = result;
result = n;
carry = sum / 10;
}
// if a carry exists we need another node to put this
if (carry != 0) {
Node n = new Node(carry);
n.next = result;
result = n;
}
return result;
}
}
How about the following logic then:
1. Create another list which is the result of two lists in first pass. The next result is always put in front of the previous result.
2. Adjust the sum and carry in next pass
3. Reverse the adjusted linked list
Time O(n)
SpaceO(1)
This will work for different length lists as well
public class SumTwoList2 {
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// traverse through the list to find the size
private int size(Node head) {
Node temp = head;
int len = 0;
while (temp != null) {
len++;
temp = temp.next;
}
return len;
}
public Node addLists(Node head1, Node head2) {
// if either of the lists are empty then take appropriate action
if (head1 == null && head2 == null) {
return null;
} else if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
Node result = null;
int l1 = size(head1);
int l2 = size(head2);
int len = 0;
int i;
// start pushing the bigger list items on the stack
if (l1 > l2) {
len = l2;
for (i = 0; i < l1 - l2; i++) {
Node n = new Node(head1.data);
head1 = head1.next;
n.next = result;
result = n;
}
} else if (l1 < l2) {
len = l1;
for (i = 0; i < l2 - l1; i++) {
Node n = new Node(head2.data);
head2 = head2.next;
n.next = result;
result = n;
}
}
// Now both lists are same length
for (i = 0; i < len; i++) {
Node n = new Node(head1.data + head2.data);
head1 = head1.next;
head2 = head2.next;
n.next = result;
result = n;
}
int sum = 0, carry = 0;
Node ptr = result;
// adjust the carry and forward it to next node
while(ptr != null) {
sum = ptr.data;
ptr.data = sum%10 + carry;
carry = sum / 10;
ptr = ptr.next;
}
// if a carry exists we need another node to put this
if (carry != 0) {
Node n = new Node(carry);
n.next = result;
result = n;
}
reverse(result);
return result;
}
public void reverse(Node head) {
if(head == null || head.next == null) {
return;
}
Node p = head;
Node q = head.next;
Node r = null;
while(q != null) {
r = q.next;
q.next = p;
p = q;
q = r;
}
head.next = null;
head = p;
}
}
@CodeNameEagle:
Nice approach man. Small correction in your code. You have forgot to add carry to ptr.data in while loop. And also move the ptr to next
while(ptr != null)
{
sum = ptr.data;
ptr.data = sum%10 + carry; // added carry
carry = sum / 10;
ptr = ptr.next; // added
}
int FindSum(node* n1, node* n2, node** r, int depth)
{
if (!n1 && !n2)
return 0;
node* result = (node*)malloc(sizeof(node));
n->value = value;
n->next = next;
*r = result;
int v1,v2,carry = 0;
if(!n1)
{
v1 = 0;
v2 = n2->value;
carry = FindSum(NULL,n2->next,&(result->next),depth+1);
}
else if(!n2)
{
v1 = n1->value;
v2 = 0;
carry = FindSum(n1->next,NULL,&(result->next),depth+1);
}
else
{
v1 = n1->value;
v2 = n2->value;
carry = FindSum(n1->next,n2->next,&(result->next),depth+1);
}
if (depth==1)
{
result->value = v1+v2+carry;
return 0;
}
else
{
int sum = v1+v2+carry;
result->value = sum%10;
return sum/10;
}
}
/// Call: FindSum(n1,n2,&result, 1)
Try this java code here....
public Link addLists (Link link1, Link link2) {
Link res = null;
Link prev = null;
Link temp = null;
int carry = 0, sum;
while (link1 != null || link2 != null) {
//sum = carry + ( (l1.data1 != null) ? l1.data1: 0) + ( (l2.data1 != null) ? l2.data1: 0);
sum = carry + link1.data1 + link2.data1;
carry = (sum >= 10)? 1 : 0; // update carry for next calulation
sum = sum % 10; // update sum if it is greater than 10
temp = new Link(sum); // Create a new node with sum as data
// if this is the first node then set it as head of the resultant list
if(res == null) {
res = temp;
} else { // If this is not the first node then connect it to the res.
prev.nextLink = temp;
}
// Set prev for next insertion
prev = temp;
// Move first and second pointers to next nodes
if (link1 != null) {
link1 = link1.nextLink;
}
if (link2 != null) {
link2 = link2.nextLink;
}
}
if (carry > 0) {
temp.nextLink = new Link(carry);
}
return res;
} // addLists()
reverse both the linked list and add it and store the result in third list.Reverse the third list in the end.
@aka : why are you reversing it ? we can add them simply by traversing both the lists node by node.
package programmingInterview;
public class LinkedListSum{
public static class List{
int value;
List next;
public List(int value){
this.value = value;
this.next = null;
}
public List(){
}
public static List addElement(List a, List b){
b.next = a;
a = b;
return a;
}
}
public static List findSum(List a, List b){
List c = new List();
List d = new List();
while(a!=null || b!=null){
if(a!=null && b!=null){
c = new List(a.value + b.value);
a = a.next;
b = b.next;
}
else if(a==null){
c = new List(b.value);
b = b.next;
}
else{
c = new List(a.value);
a = a.next;
}
d = List.addElement(d, c);
}
return d;
}
public static void print(List lls) {
while(lls.next != null){
System.out.print(lls.value+"-->");
lls = lls.next;
}
System.out.println(lls.value+"-->NULL");
}
}
@aka : I think he's traversing both the list in a while loop till the end and adding the numbers simultaneously.
i.e.
Linkedlist 1 = 5 -->4-->2-->9
LinkedList 2 =7-->3-->1-->1
Result = 12-->7-->3-->10
Here's the pseudo code :
1. Create three pointers p,q, result and point it to the head of the given linked lists.
2. if p, q are both not null then add p->data and q->data and store it in result and set p = p->next and q=q->next.
else if p is not null then store p->data in result and set p = p->next.
else if q is not null then store q->data in result and q = q->next.
else if both pointers are null goto step 4.
3. Goto step 2.
4. return result.
// here in our logic we 1st calculate the value of each linked list separately
int sum(struct node *f,struct node *s)
{
static su,sf,ss; //sum for total sum SF for the number in first SS number in second
if(f==NULL && s==NULL)
{
su=sf+ss;
return ;
}
else if(f==NULL && s!=NULL)
{
ss=ss*10+s->data;
sum(f,s->link);
}
else if(f!=NULL && s==NULL)
{
sf=sf*10+f->data;
sum(f->link,s);
}
else
{
sf=sf*10+f->data;
ss=ss*10+s->data;
sum(f->link,s->link);
}
return su;
}
Hi, here's one piece of code which was developed with reference to the one I noticed at geeksforgeeks
public Link addLists (Link link1, Link link2) {
Link res = null;
Link prev = null;
Link temp = null;
int carry = 0, sum;
while (link1 != null || link2 != null) {
//sum = carry + ( (l1.data1 != null) ? l1.data1: 0) + ( (l2.data1 != null) ? l2.data1: 0);
sum = carry + link1.data1 + link2.data1;
carry = (sum >= 10)? 1 : 0; // update carry for next calulation
sum = sum % 10; // update sum if it is greater than 10
temp = new Link(sum); // Create a new node with sum as data
// if this is the first node then set it as head of the resultant list
if(res == null) {
res = temp;
} else { // If this is not the first node then connect it to the res.
prev.nextLink = temp;
}
// Set prev for next insertion
prev = temp;
// Move first and second pointers to next nodes
if (link1 != null) {
link1 = link1.nextLink;
}
if (link2 != null) {
link2 = link2.nextLink;
}
}
if (carry > 0) {
temp.nextLink = new Link(carry);
}
return res;
} // addLists()
public static class Node {
public int digit;
public Node next;
public Node(int digit) {
this.digit = digit;
}
}
public static Node add(Node a, Node b) {
Node _a = a;
Node _b = b;
Node c = new Node(0);
Node _c = c;
int extras = 0;
while (_a != null) {
int sum = _a.digit + _b.digit;
if (sum < 9) {
for (int i = 0; i < extras; ++i) {
_c.next = new Node(9);
_c = _c.next;
}
_c.next = new Node(sum);
_c = _c.next;
extras = 0;
} else if (sum == 9) {
++extras;
} else {
++_c.digit;
for (int i = 0; i < extras; ++i) {
_c.next = new Node(0);
_c = _c.next;
}
_c.next = new Node(sum % 10);
_c = _c.next;
extras = 0;
}
_a = _a.next;
_b = _b.next;
}
for (int i = 0; i < extras; ++i) {
_c.next = new Node(9);
_c = _c.next;
}
if (c.digit == 0) {
c = c.next;
}
return c;
}
public static List findSum(List l1, List l2){
int sum1=0;
int sum2=0;
//Find the integer stored in list1
for (int i =0; i<l1.size();i++){
sum1= sum1*10+l1.get(i);
}
//Find the integer stored in list1
for (i =0; i<l2.size();i++){
sum1= sum1*10+l2.get(i);
}
//Find their sum
int result=sum1+sum2;
//The resultant linked list
List<Integer> resultList= new LinkedList<Integer>();
while(result!=0){
int mod=result%10;
result=result/10;
resultList.addFirst(mod);
}
return resultList;
}
addtwolists(node *p,node *q)
{
int carry=0,num,num1,num2;
node *temp1=p,*temp2=q,*list3=NULL;
while(temp1!=NULL||temp2!=NULL)
{
if(temp1==NULL)
{
num1=temp2->data+carry;
if(carry==1)
carry=0;
if(num1>=10)
{
num1=num1-10;
carry=1;
}
add(&list3,num1);
}
else
{
if(temp2==NULL)
{
num2=temp1->data+carry;
if(carry==1)
carry=0;
if(num2>=10)
{
num2=num2-10;
carry=1;
}
add(&list3,num2);
}
else
{
num=temp1->data+temp2->data+carry;
if(carry==1)
carry=0;
if(num>=10)
{
num=num-10;
carry=1;
}
add(&list3,num);
}
}
if(temp1!=NULL)
temp1=temp1->next;
if(temp2!=NULL)
temp2=temp2->next;
}
if(carry==1)
{
add(&list3,carry);
carry=0;
}
return list3;
}
add(node **p,int num)
{
node *temp,*r;
temp=*p;
if(*p==NULL)
{
temp=malloc(sizeof(node));
temp->data=num;
temp->next=NULL;
*p=temp;
}
else
{
temp=*p;
while(temp->next!=NULL)
temp=temp->next;
r=malloc(sizeof(node));
r->data=num;
r->next=NULL;
temp->next=r;
}
}
What's the correct result of the example?
1) 12 -> 7 -> 3 -> 10
2) 1 -> 2 -> 7 -> 4 -> 0
3) 2 -> 8 -> 3 -> 0 -> 1
The answer depends the three cases. I don't see a clear clue what the problem is.
As for the 1) and 3), the solution is quite straightforward. However, we should visit the two lists in advance, reversing or calculating the merging point.
Looks to be simple .
bool returnsum(Node **headnode1, Node **headnode2, Node **sum)
{
int data1= 0;
int data2 = 0;
int sumNode = 0;
Node *newNode = *sum;
Node *temp1 = *headnode1;
Node *temp2 = *headnode2;
if(*headnode1 == NULL && *headnode2 == NULL)
{
return false;
}
while(temp1 || temp2)
{
if(temp1)
{
data1 = temp1->data;
temp1 = temp1->next;
}
else
{
data1 = 0;
}
if(temp2)
{
data2 = temp2->data;
temp2 = temp2->next;
}
else
{
data2 = 0;
}
newNode ->data = data1 + data2;
if(temp1 || temp2)
{
newNode->next = new Node();
newNode = newNode->next;
}
}
}
public Linkedlist sum(Node aHead, Node bHead)
{
if(aHead.next == null || bHead.next == null)
{
Linkedlist ll = new Linkedlist();
Node h = new Node();
h.data = (aHead.data + bHead.data);
h.next = null;
ll.head = h;
return ll;
}
else
{
Linkedlist l = sum(bHead.next, aHead.next);
Node n = new Node();
n.data = aHead.data + bHead.data + l.head.data/10;
l.head.data = l.head.data % 10;
n.next = l.head;
l.head = n;
return l;
}
}
//Code for n-length linked list with result list of size 'n' preallocated
void findSUM( Node l1, Node l2, Node result){
if( (l1==NULL && l2==NULL) || result==NULL) return;
if(l1!=NULL) {result=l2; return;}
else {result=l1; return;}
carry=sumHelper(l1, l2, result);
if(carry>0)
result.data=result.data+(carry*10);
}
int sumHelper(Node l1, Node l2, Node result){
if(l1==NULL || l2==NULL)
return 0;
carry=sumHelper(l1.next, l2.next, result.next);
result.data=(l1.data + l2.data+ carry)%10;
return (l1.data + l2.data + carry)/10;
}
// Recursive approach
LinkedList* addLinkedList(LinkedList* list1, LinkedList* list2) {
LinkedList* sumNode = NULL;
if (list1 == NULL && list2 == NULL )
return NULL ;
else {
int carry = 0;
LinkedList* prevSumNode =
addLinkedList(list1 != NULL ? list1->next : NULL,
list2 != NULL ? list2->next : NULL);
sumNode = malloc(sizeof(LinkedList));
sumNode->next = NULL;
int data1 = list1 != NULL ? list1->data : 0;
int data2 = list2 != NULL ? list2->data : 0;
if (prevSumNode != NULL && prevSumNode->data > 10)
{
carry = prevSumNode->data / 10;
prevSumNode->data = prevSumNode->data % 10;
}
sumNode->data = data1 + data2 + carry;
sumNode->next = prevSumNode;
}
return sumNode;
}
template <class V>
node<V>* add_reverse_order(node<V>* nod1, node<V>* nod2, int& carry, int level) {
if (nod1 == NULL && nod2 == NULL) {
return NULL;
} else {
node<V>* nod3 = new node<V>();
nod3->set_next(add_reverse_order(nod1->return_next(), nod2->return_next(), carry,
level + 1));
int sum = nod1->return_value() + nod2->return_value() + carry;
carry = sum / 10;
int unit_place = sum % 10;
if (level != 0) {
nod3->set_value(unit_place);
} else {
nod3->set_value(sum);
while (nod3 != NULL) {
cout << nod3->return_value() << "--->";
nod3 = nod3->return_next();
}
}
return nod3;
}
}
- Ravi June 07, 2013