Microsoft Interview Question for Software Engineer in Tests


Country: -




Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<stdio.h>

#include<stdlib.h>

struct linkedlist
 {
    int n;
    struct linkedlist *next;  


 };
typedef struct linkedlist node;

int sum(node *str1,node *str2,node **str3)
  {
       int a=0;
      if(str1 !=NULL && str2 !=NULL )
          {
                node *nw=(node *) malloc(sizeof(node));
                //printf("Hello\n");
                
                a=(str1->n) + (str2->n) + sum(str1->next,str2->next,str3);
                nw->n=a % 10;
                nw->next=(*str3); 
                *str3=nw;
               // printf("%d",((*str3)->n));
               return a/10;

          }
          return 0;
}

   node * createlinkedlist(node  *str)
    { 
       node *nw;
       int i=0,k;
       printf("enter how many nos \n");
       scanf("%d",&k);
       while(i<k)
        {
               node *nw=(node *) malloc(sizeof(node));
                printf("enter no : ");
                scanf("%d",&(nw->n));
               if(i==0)
                 {
                   nw->next=NULL;
                   str=nw;
                  } 
               else{ nw->next=str;
                str=nw;}
                i++; 
               
        }
 
          return str;
   }


     void display(node *str)
      {
         while(str != NULL)
          {
              printf("%d\t",str->n);
             str=str->next;

          }

        printf("\n");
      }
   
   
   void main()
    {
          node *str1,*str2,*str3,*nw;
          int carry;  
          str1=str2=str3=NULL;
          str1= createlinkedlist(str1);
          str2=createlinkedlist(str2); 
          display(str1);  
          
          carry=sum(str1,str2,&str3);
           if(carry !=0)
            {
              nw=(node *) malloc(sizeof(node));
              nw->n=carry;
              nw->next=str3;
              str3=nw; 
            }


          display(str2);
          
          display(str3); 
          

    }

- Ravi June 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- shaktiman April 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- code_monkey May 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shaktiman May 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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??

- Fan May 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is elegant but it needs some slight modifications in order to work as it is supposed to.

- Fan May 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Varun April 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes for varied length list it wont work. For simplicity I have been asked to assume both list sizes are same.

Additionally we can not reverse input list as specified in the question.

- shaktiman April 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- CodeNameEagle April 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can not use additonal data structure e.g. explicit stack

- shaktiman April 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 April 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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
}

- f2003062 May 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks f2003062, I really do not remember how I missed that. Its so basic. Thanks for the correction. I have fixed it now.

- CodeNameEagle May 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- CareerCup May 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First List       : 1-->2-->3

            1*100 + 2*10 + 3*1 = 123

    Second List  : 8-->9-->10

            8*100 + 9*10 + 10*1 = 900

    Result List    :

123

       +  900

       -----------

         1023

add 1023 to Singly List.
if(ans.length==4)
{
	add first two digit to first node
}
else
{
	add one digit to node
}

- Hardik Sondagar May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- muks May 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

reverse both the linked list and add it and store the result in third list.Reverse the third list in the end.

- aka May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@aka : why are you reversing it ? we can add them simply by traversing both the lists node by node.

- Ashish May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashish: can you traverse backward in a single linked list?

- ak May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need to traverse backward ? if the above problem also consider carry then we can pass it by using a variable.

- Ashish May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
	}


}

- Rohit May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

logic please?

- aka May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Ashish May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Ashish
Linkedlist 1 = 5 -->4-->2-->9
LinkedList 2 =7-->3-->1-->1
Result = 12-->7-->3-->10 Wrong Answer.
Correct Answer 12-->7-->4-->0

- ankitjaingc May 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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;
}

- Anonymous May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- muks May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- rixcat May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sites.google.com/site/spaceofjameschen/home/linked-list/add-two-lists

- Anonymous May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Sam May 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- kaushal yadav May 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- liuml07 May 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

}

- Anonymous May 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Anonymous May 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about traversing the linked list and storing the result.
Example:
9->8->7->6
5->4->3->2

now, we get 4->2->0->8
and carry as 1->1->1->0
shift it and add again.so,

0->4->2->0->8
1->1->1->0

now we get the answer.

- infinite_loop June 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

- ganeshjwhr June 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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;
}

- Prabhakar June 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- PJ June 29, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More