## Amazon Qualcomm Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: India
Interview Type: In-Person

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

Following code is tested. It handles the case where first list is longer than the second, or second is longer than the first as well as when they are of equal length.

``````int FindLength(Node* n) { // find the length of a given linked list.
int ret = 0;
while(n) {
ret++;
n = n->next;
}
return ret;
}
Node* Add(Node* list1, Node* list2) { // this function is called first
int state = FindLength(list1) - FindLength(list2);
// if state > 0, list1 is longer
// if state < 0, list2 is longer
// if state == 0, list1 and list2 is of same length
int carry = 0;
Node* ret = Add2(list1, list2, carry, state); // add the two lists
if ( carry > 0 ) { // handle carry for the leftmost digit
Node* temp = new Node(carry);
temp->next = ret;
ret = temp;
}
return ret;
}
Node* Add2(Node* p1, Node* p2, int& carry, int state) { // helper function
if ( p1 == NULL && p2 == NULL ) // if both are NULL, we are at the end
return NULL;
Node* ret = new Node(0); // create new node to return
if ( state > 0 ) { // p1 is still longer than p2
// only advance p1's pointer and decrease state
ret->next = Add2(p1->next, p2, carry, state-1);
ret->data = carry + p1->data; // just sum carry and p1's data
}
else if ( state < 0 ) { // p2 is still longer than p1
// only advance p2's pointer and increase state
ret->next = Add2(p1, p2->next, carry, state+1);
ret->data = carry + p2->data; // just sum carry and p2's data.
}
else { // p1 and p2 are of same length
// advance both pointers, state should stay untouched from now on(0).
ret->next = Add2(p1->next, p2->next, carry, 0);
ret->data = carry + p1->data + p2->data; // sum carry and both digits
}
carry = ret->data / 10; // calculate new carry
ret->data %= 10;        // update the current data to be smaller than 10
return ret;             // return the new node``````

}

Comment hidden because of low score. Click to expand.
0

using recursion here is an overkill (also giving that the lists can be of arbitrary length). can be done within a single loop

Comment hidden because of low score. Click to expand.
0

this is fine did you handled 8888889 and 111

Comment hidden because of low score. Click to expand.
0

Tested it when I saw your comment. The code returned the correct result.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

I first find the difference in length of both linked lists and save this value in a variable called state. If state is positive, the first list is longer, if it's negative, the second list is longer and if it's 0, their lengths are equal.

To handle the carry properly, and to handle the difference in length, we need to do the addition starting from the end of the lists. So, I wrote a recursive function (Add2) that gets the then current head of the linked lists, a reference to int to pass the carry, and the value of the state variable. As long as the state variable is nonzero, we know that the two linked lists this function gets are not equal in length. That's why if the state variable is positive, we only add the value from the first linked list and if the state variable is negative, we only add the value from the second linked list.

The critical part happens here. Note that we only advance the pointer of the longer linked list while recursively calling Add2 at this point. The other important part is updating the state variable for the next call. We either increment or decrement the state value (whichever brings it closer to 0).

Only if they are equal in length, we add both of them and advance both pointers for the next call of Add2.

After we do the additions, we update the value of that node to be less than 10, and calculate the new carry. Since the carry variable is a reference, we can successfully pass this value to the previous call of our function. At the end, Add2 returns the head of the then current result. Inside Add, we also need to take care of the carry for cases where the result has more digits than both the first linked list and second linked list (e.g: 999+1). So if the carry is greater than 0, we create another node and put that node at the head of the resulting list.

Comment hidden because of low score. Click to expand.
0

Since you have calculated the lengths,
move the longer list's head by (|l1-l2|) nodes, and then just handle the case of equal lengths with carry at the head of longer list
...
it will save some un wanted code

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

In interviews like that of Amazon, please don't expect the interviewer to give the expected complexity, etc. They want us to give an optimal solution. Gone are the days of merely solving problems. This is the time of scalability. So better make ur solutions how-much-ever optimal in the first go itself. My own experience with Amazon, I had high hopes, but they said, my problem solving skills are bad, though i gave all solutions. But not optimal ones.

Comment hidden because of low score. Click to expand.
2
of 4 vote

There could be multiple approaches. Two of them are listed below:
Approach 1: Convert the linked lists to numbers. Add them. And then convert back the resultant number to a linked list.
Approach 2: Take two stacks and push a linked list to a stack. After done pushing, simply start popping the stacks, add the numbers, get the carry over, generate another node with the result and add to front to a new linked list.
I prefer the second approach as this is less prone to errors while coding and faster when in-built library functions for stacks are used, although it takes memory with order of m+n where m and n are lengths of the linked lists.

Comment hidden because of low score. Click to expand.
0

1)I don't think they would allow you to do that. If you were to add numbers, he would have given the numbers.

Comment hidden because of low score. Click to expand.
-2

what is this ? "practice coding question for dummies ?" ))

Comment hidden because of low score. Click to expand.
0

The first approach might lead to overflow if the list is too huge such that the sum of its elements is beyond the range of int/long.

The second approach is the only one that looks achievable. we can do something like this:

1. find the length of 2 lists => len_l1 and len_l2(lets say len_l1 > len_l2)
2. traverse the bigger list skipping (len_l1 - len_l2) nodes in l1.

3. now keep pushing teh current top of each list into the stack and call step 3 recursively passing (l1->next, l2->next).

4. in the recursive method implementing step 3, check if(nodeFromListOne->next == NULL && nodeFromListTwo->next == NULL). if so, this is the last node and we must start returning (popping from stack) after this instead of contuining with recusrion.

5. return the sum of digitList1 and digitList2 as well as the carryover value.

6. in the caller stack (to whom these values are returned), use the carry over value returned for summation again. also to store the sum, we can either create a new list or update either list1 or list 2 with the sum

Comment hidden because of low score. Click to expand.
0

if input is like more than 9000000000000000000 u should not have data type to store this as number

Comment hidden because of low score. Click to expand.
0

manjunath426jc:
The difference between the recursive solution by 'crdmp' and the 2nd approach of 'Victor' is that in recursive solution, the system(language-library and/or OS) will maintain a stack where as in 'Victor' case the program will explicitly maintain a stack.

To me none of them are reversing the list and using explicit stack is always better than a recursive solution since system's method stack consumes more memory and cause performance overhead than explicit stack maintenance.

In fact my vote goes to Victor's 2nd approach.

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

``````/*Solution Code to algorithm suggested by lanse.cse
1. reverse the lists.
2. add them digit by digit and construct the result list.
3. reverse the result list.
NOTE: This code demonstrates the solution. The code will fail for invalid or no input and maybe other cases. Output for the following code : 9,1,3,1,3,8
*/
#include <iostream>
using namespace std;
//! Node to store digits
struct Node{
short digit;	//doesn't make a difference if I use short or int
Node* next;
};
//!Function reverses an input list
curr->next = NULL;
while(true){
break;
}
nxt	   = nxt->next;
}
}
//! Function to compute the sum of two input lists. Complexity: O(m+n), sizes of lists m,n
void sumOfLists(Node*& list1, Node*& list2, Node*& result){
// Reverse lists: Time: O( m + n). operating on input lists to save space complexity
reverseList(list1);
reverseList(list2);
Node* ptr;
ptr = new Node();
result = ptr;
int n1=0,n2=0,sum=0,carry=0;
bool n1flag=true,n2flag=true;
while(n1flag || n2flag){
n1= n1flag?list1->digit:0;
n2 = n2flag?list2->digit:0;
sum = n1+n2+carry;
carry = (sum>=10)?1:0;
ptr->digit = (sum-10*carry);
if(n1flag)
if(list1->next==NULL)
n1flag = false;
else
list1 = list1->next;
if(n2flag)
if(list2->next==NULL)
n2flag = false;
else
list2 = list2->next;
if(n1flag || n2flag){
ptr->next = new Node();
ptr = ptr->next;
}else
ptr->next = NULL;
}
reverseList(result);
}
void printListValues(Node*& list){
Node* ptr=list;
do{
cout<<ptr->digit<<",";
ptr = ptr->next;
}while(ptr->next!=NULL);
cout<<ptr->digit<<endl;
}
int main(){

//construct two lists, replace the below digits to test your values
int myNum1[] = {9,1,2,3,2,9};//First list 912329,
int myNum2[] = {0,8,0,9};  //second list 0809
Node *newNd1, *num1, *num2, *result;
newNd1=new Node;num1 = newNd1;
int sz = sizeof(myNum1) / sizeof(int);
for(int i=0;i<sz;++i){
newNd1->next = (i==sz-1)?NULL:(new Node);
newNd1->digit = myNum1[i];
newNd1=newNd1->next;
}
newNd1 = new Node;num2 = newNd1;
sz = sizeof(myNum2) / sizeof(int);
for(int i=0;i<sz;++i){
newNd1->digit = myNum2[i];
newNd1->next = (i==sz-1)?NULL:(new Node);
newNd1=newNd1->next;
}
//Find sum
sumOfLists(num1,num2,result);	//. Result should be 913138
printListValues(result);
}``````

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

how abt this idea?
first we will fetch the lengths. then we will add 0's in the heads place of smaller linkedlist till the lingth of both becomes same..
lets assume linked list numbers are 999 and 999
the heads 99(this 9,9 are both the heads of two linked lists) will become 18. we will keep 18 . bein in the same place , we will calculate , the next's su, if there is carry , we will increment , the currnt number.then we will move to next. will repeat the same while ->next != null.

Comment hidden because of low score. Click to expand.
0

How about for the case 909 + 999 ?

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

hw abt using stack n push n pop n add

Comment hidden because of low score. Click to expand.
0

You can use but that would add O(n) space to the complexity. It's better to use the concept of reversing singly link list.

@Others: suggest any other better solution.

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

I have a feeling that the question is not complete. because here's a bruteforce O(n) solution.

``````Assume 'n' elements in each linked list,
construct an array from each linked list,
start from the end of the arrays and keep adding elements and storing into another array with carry. The max size of the second array can be 2n.
Build another linked list from the result array.
Time complexity: O(n + n + 2n + 2n) => O(6n) => O(n)
Space complexity: O(n + n + 2n) => O(4n) => O(n)``````

so what are we trying to optimize? space , time ? or something else?

Comment hidden because of low score. Click to expand.
0

Question is incomplete as it doesn't give any constrain, though reversing the list sounds like a better solution. Anyways you can tell both the solutions and let the interviewer choose.

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

So can we just process the linked lists and get the number? I.e. multiply by 10 for each -> next. Or are we assuming the numbers are just too big to fit in a long?

Comment hidden because of low score. Click to expand.
0

it is possible that the number could be 1000 digits, until now we dont have any standard datatype that stores 1000 digits. so consider we are building a new datatype which can add astronomical numbers

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

I mentioned the pushing into stack answer. But interviewer was not happy.

How does reversing link list work?

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

``````lets say the numbers are 1->2->3 and 1->2
After reversing the lists look like 3->2->1 and 2->1
Now add the two lists node by node and properly take care of the carry over of the addition of the nodes, if any.
so, the resultant added list will look like 5->3->1
Now reverse the "resultant added list" to get the result of addition of two original lists. That is 1->3->5 is the actual answer.``````

Comment hidden because of low score. Click to expand.
0

For addition, instead of reversing the link list, shouldn't we make the exact no by traversing through the list. because if we reverse the link list we are changing the input also.
And building the exact number is easier than reversing the link list.

1->2->3.
no will be= (1*10+2)*10+3=123
1->2
no will be= 1*10+2=12

Store the resulting number in Link list. that can be done in reverse order. (because we will do divide by 10).

In this approach we don't have to worry about carry over also.

Comment hidden because of low score. Click to expand.
0

ashpiy, how would handle the number if it exceeds the integer range..how would you store the numbers before addition and the result after addition..?

Comment hidden because of low score. Click to expand.
0

Yeah, that's correct. I did not think about the carry.

Comment hidden because of low score. Click to expand.
0

Sorry, I did not think about that.

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

Guys, there is some amount of repeated code. Any optimized version would be highly appreciated..
Please suggest any other better approach..
Time Complexity is O(n).

``````#include <stdio.h>
#include <stdlib.h>

struct Number
{
int key;
struct Number* next;
};

typedef struct Number node;

void createDigits(node **);
void printDigits(node *);
void reverseDigits(node **);
void addDigits(node *, node *, node **);

int main()
{

printf("Create the first number..\n");
{
printf("First Input is not correct..\n");
return 1;
}
printf("Create the second number..\n");
{
printf("Second Input is not correct..\n");
return 1;
}
printf("Number 1: \n");
printf("\n");
printf("Number 2: \n");
printf("\n");
printf("Number 1 reversed..\n");
printf("\n");
printf("Number 2 reversed..\n");
printf("\n");
printf("Add the two reversed numbers node by node..\n");
printf("Reversing the result to get the actual result..\n");
printf("sum of two numbers in linked representation is: \n");
printf("\n");
return 0;
}

void createDigits(node **list)
{
int digit = 0;
node* tNode = NULL;
printf("Enter positive digits to insert..(enter -999 to exit)\n");
scanf("%d",&digit);
if(digit == -999)
{
printf("Input completed..\n");
}
else
{
if(NULL == *list)
{
*list = (node *)malloc(sizeof(node));
(*list)->key = digit;
(*list)->next = NULL;
createDigits(list);
}
else
{
tNode = *list;
while(tNode->next != NULL)
tNode = tNode->next;
tNode->next = (node *)malloc(sizeof(node));
tNode = tNode->next;
tNode->key = digit;
tNode->next = NULL;
createDigits(list);
}
}
}

void printDigits(node* list)
{
if(list->next != NULL)
{
printf("%d->",list->key);
printDigits(list->next);
}
else if(list->next == NULL && list->key != -999)
{
printf("%d\n",list->key);
}
else
{
printf("Empty List..\n");
}
}

void reverseDigits(node** list)
{
node* temp1 = *list;
node* temp2 = NULL;
node* temp3 = NULL;

while(temp1)
{
*list = temp1;
temp2 = temp1->next;
temp1->next = temp3;
temp3 = temp1;
temp1 = temp2;
}
//return *list;
}

{
node* temp = NULL;
int keyVal = 0;
static int pass = 0;
{
{
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
pass = 1;
}
else
{
pass = 0;
}
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal-10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
}
{
{
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
pass = 1;
}
else
{
pass = 0;
}
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal%10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
}
{
{
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
pass = 1;
}
else
{
pass = 0;
}
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal-10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
}
else if(pass == 1)
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
temp->key = pass;
temp->next = NULL;
}
}``````

Comment hidden because of low score. Click to expand.
0

it looks very big code. I would still suggest not to do reverse link list.

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

sum = atoi(list1) + atoi(list2)
where atoi is modified version that operates on list of numbers.
Then, itoa(sum), which ouputs as a list of numbers.

Comment hidden because of low score. Click to expand.
0

Looks fine for small numbers, how about large numbers that exceed integer ranges..

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

Is the following rephrase of th equestion correct (rephrased/introduced words in quotes):

You have two "set" of numbers represented by "two" linked lists, where each node contains a single digit. Write a function that adds the two numbers "in the corresponding nodes" and returns the sum as a "third" linked list

Comment hidden because of low score. Click to expand.
0

This is the different solution than others, and looks better also.

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

By reversing LinkList is very lengthy.

We have two Linklist A and B of length x and y(we can find length by simple traversing)

Now There may be three condition:(x=y,x>y,x<y):
_____________________________________________________________________________________
[1]:length of list A and length of List B are same (x=y):
In this case we can use simple recursion which will start from the end of list and proceed to front.recursive function will return carry digit(1 OR 0).
**********
+
**********
=
**********
NOTE: '*' can be any digit (0-9)
____________________________________________________________________________________
[2]:if length of List A is greater then length of list B(x>y):
In this case we will divide our bigger link list into two part (A1 and A2).First part(A1) will be of length (x-y) and second part(A2) will be of length (y). Now second part(A2) of List A and B are of same length (y).we can add it by simple recursion as we did in condition [1].After adding these two (A2 and B) we will append first part(A1) of list A if there is not carry digit in (A2+B).If there is any carry digit in (A2+B) we will apply recursion this time in first part(A1)of A
and add one at the end of A1 and then appent the modified A'1 with (A2+B).We will get A'1(A2+B).The resultent sum.
*******************(x) *******A1(x-y) ************A2(y)
+ + ************B(y)
**********(y)
= *******A1(x-y) ************[A2+B](y)
=
*****************(x) = *****************[A1][A2+B](x)

___________________________________________________________________________________
[3]:if length of List A is lesser then length of list B(x<y):
Same as condition [2] by replacing x with y.

Recursive Function:

{
int i=0;;
{
}
if(A->info>9)
{
i=1;
}
return i;
}

__________________________________________________________________________________

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

*******A1(x-y) ************A2(y)
+ ---------------************B(y)

= *******A1(x-y) ************[A2+B](y)
= *****************[A1][A2+B](x)

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

Hello PKT
I feel a lil problem there!!! If u r adding the lists from end are u assuming them to be pointing to their prev. node??
Otherwise u need to use linked List reversal!!

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

Simple solution. Complexity - O(n)

int carry = 0;
while(nodenum1->next!=null or nodenum2->next!=null)
{
addition = carry + nodenum1->data + nodenum2->data;
carry = (nodenum2->data)/ 10;
}

reverse(nodenum2)

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

***Ignore the above solutions***

Simple solution. Complexity - O(n)

int carry = 0;
while(nodenum1->next!=null or nodenum2->next!=null)
{
addition = carry + nodenum1->data + nodenum2->data;
carry = (nodenum2->data)/ 10;
}

//Copy the remaining elements of larger list in the nodenum2

//reverse the resultant
reverse(nodenum2)

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

why all you guys checking (nodenum1->next!=null or nodenum2->next!=null) only. What if both lists end but there is still carry to consider. Here is simple test case.

list1 contains single element 5 and list2 contains any element >5

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

Guys Here is a solution without reversing the link lists
Time Complexity = O(n)
Works for any length of linked lists

``````l1 = length_linklist(head1);
while(l1<l2){
temp = create_node(0);
l1++;
}
while(l2<l1){
temp = create_node(0);
l2++;
}

``````void add(node *head1,node *head2){
carry = sum/10;
}
}``````

Comment hidden because of low score. Click to expand.
0

since you are adding 1 digit numbers you can skip % and use sum - 10, it's much faster.

Also notice that curry=sum/10 is always 0 as it's a int/int = int

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

Guys Here is a solution without reversing the link lists
Time Complexity = O(n)
Works for any length of linked lists

``````l1 = length_linklist(head1);
while(l1<l2){
temp = create_node(0);
l1++;
}
while(l2<l1){
temp = create_node(0);
l2++;
}

``````void add(node *head1,node *head2){
carry = sum/10;
}
}``````

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

Can perform this, by traversing the two lists and getting the two numbers. Then adding the two numbers through simple int addition and saving the result in another link list.

a. getting int
while( a != NULL)
num = num*10 + a->value;

num_final = num1+num2

get digits of final and save it in another list.

Comment hidden because of low score. Click to expand.
0
of 2 vote

The following 'sum' method will return the requirement .

``````private static int sum(LinkedList l1, LinkedList l2) {
int sum = 0;
int decimal = 1;
int max = 0, min = 0;
if (l1.size() > l2.size()) {
max = l1.size() - 1;
min = l2.size() - 1;
} else {
max = l2.size() - 1;
min = l1.size() - 1;
}
for (int i = max; i >= 0; i--) {
if ((l1.size() - 1) == max) {
sum = sum + (decimal * (Integer) (l1.get(i)));
} else {
if (min >= 0) {
sum = sum + (decimal * (Integer) (l1.get(min)));
min--;
}
}
if ((l2.size() - 1) == max) {
sum = sum + (decimal * (Integer) (l2.get(i)));
} else {
if (min >= 0) {
sum = sum + (decimal * (Integer) (l2.get(min)));
min--;
}
}
decimal = decimal * 10;
}
return sum;
}``````

AnanthaNag KUNDANALA

Comment hidden because of low score. Click to expand.
0

but lists can be of arbitrary length thus you can get an overflow in 'sum'

Comment hidden because of low score. Click to expand.
0

Overflow ???

will you please give me an example ?

Comment hidden because of low score. Click to expand.
0

point is you accumulate your resulting sum in an integer (not in a list) consider adding two very long lists like

1->1->1->1-> ... ->1->1

Comment hidden because of low score. Click to expand.
0

got you. So, I guess replacing 'int' with some other bigger primitive datatype (like long), I will be in safe side. Is n't it ?

Comment hidden because of low score. Click to expand.
0

well, probably this stuff should be clarified with an interviewer:
this also shows that you are aware of the problem..
if the lists contain thousands of nodes, any standard number type would give an overflow, thus the general solution is to use a list for the resulting sum as well

Comment hidden because of low score. Click to expand.
0

yup. thanks a ton for enlightenment. Till now, I never thought of overflow of additions & other mathematical operations with respect to the range of the primitive datatypes. Thanks once again.

Comment hidden because of low score. Click to expand.
0

And may I have you in my mail contacts list? If you have no issues to be in my contacts, please revert me at kundanala@gmail.com

Comment hidden because of low score. Click to expand.
0

Kundan I need second idea on my algo also.. Please comment.

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

let me try this...
start parsing both the link list one node at a time.. to find out which is the largest one and what is the diff in the length..
suppose list1 1->2->3->4
and list2 5->3->4->6->9->2->1
given example L1=4 L2=7 and diff=3

create a function like below..

it can be passed to function

{
static int carry;
int sum,remainder;
Node *temp_node;

if(N1==NULL || N2==NULL)
return NULL;

if(size<=diff)
{
size++;
temp_node=(Node*)malloc(sideof(Node*));
sum=N2->value+carry;
}
else
{
size++;
temp_node=(Node*)malloc(sideof(Node*));
sum=N1->value+N2->value+carry;
}

carry=sum/10;
remainder=sum%10;

temp_node->value=remainder;
return temp_node;
}

tere might more exception handling and we need to take care.. but this is my over all idea..

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

``````typedef struct list_t{
int x;
struct list_t* next;
} list_t;

// add two lists and return a list
int s;
list_t* least=NULL; //pointer to the sum list least impotant digit
list_t* most=NULL; //pointer to the sum list most impotant digit
list_t* tmp=NULL;

// while there are 2 digits, add them
while( A != NULL && B != NULL){
s = A->x + B->x;
// initialize sum list
tmp = malloc(sizeof(list_t));
if(least == NULL){
least = most = tmp;
}
// add either 1 or 2 digits
if(s<9){
tmp->x = s;
tmp->next = NULL;
most->next=tmp;
most=tmp;
}
else{
tmp->x = s -10;
tmp->next = malloc(sizeof(list_t));
tmp->next->x = 1;
tmp->next->next=NULL;
most->next=tmp;
most=tmp->next;
}
A=A->next;
B=B->next;
}
while( A != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
A = A->next;
most = most->next;
}
while( B != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
B = B->next;
most = most->next;
}
return least;
}``````

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

``````LinkedList<Integer> ll = new LinkedList<Integer>();
int num1 = 0;
int num2 = 0;
for(int i =ll1.size()-1 ; i>=0;i-- ){
int temp = ll1.get(i);
for(int j =0;j<i;j++){
temp=temp*10;
}
num1=num1+temp;
}
System.out.println(num1);

for(int i =ll.size()-1 ; i>=0;i-- ){
int temp = ll1.get(i);
for(int j =0;j<i;j++){
temp=temp*10;
}
num2=num2+temp;
}
System.out.println(num2);

System.out.println("num1+num2 = "+(num1+num2));``````

This should do!!

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

``````int FormNumber( Node *n )
{
if( n == NULL )
return 0;
static int sum = 0 , i =0;
FormNumber( n->next );
sum = sum + (n->data)* pow( 10 , i );
i++;
return sum;
}

int Add( Node *h1 , Node *h2 )
{

return FormNumber(h1) + FormNumber(h2 );
}``````

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

int FormNumber( Node *n )
{
if( n == NULL )
return 0;
static int sum = 0 , i =0;
FormNumber( n->next );
sum = sum + (n->data)* pow( 10 , i );
i++;
return sum;
}

int Add( Node *h1 , Node *h2 )
{

return FormNumber(h1) + FormNumber(h2 );
}

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

``````// Sum 2 lists
{
int carry = 0, sum = 0;

return NULL;
else
{
// Both list have elements
{
if(sum > 9)
{
carry = (sum % 10) + 1 ;
printf("Sum : %d Carry : %d\n", sum, carry);
sum = sum - carry;
}else
carry = 0;
printf("Sum : %d Carry : %d\n", sum, carry);

// First node
else

}

// Both of them are empty
{
if(carry == 0)
else
{
}
}
{
if(carry == 0)
{
}
else
{
{
if(sum > 9)
{
carry = (sum % 10) + 1 ;
sum = sum - carry;
}
else
carry = 0;

}
}
}
{
if(carry == 0)
{
}
else
{
{
if(sum > 9)
{
carry = (sum % 10) + 1 ;
sum = sum - carry;
}
else
carry = 0;

}
}
}
}
}``````

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

Hope this solution will also work.
step 1: Calculate the length of both LinkList , say L1 and L2
step 2: Calculate the difference d, and find out which is longer.
step 3: Traverse the longer List for 'd' number of nodes.
step 4: Now start adding the nodes value of both LinkList and keep the Sum in longer List L1.
step 5: This way longer List L1 will have the its own starting number and Sum of each digit.
step 6: Finally create a function which have 'carry' as Static variable and traverse from end of a linklist using recursion. Use mod function to get the 'carry' part of each node starting from the end. And add this carry to previous node(in recursion). this way carry will propagate in backward direction.
step 7: If the carry still have some value when we come to first node then create a new node and add to the starting of the Linklist.

What say Guys..?

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

reverse both the list, soppose l1 = 1->2->9 and l2= 8->9
so l1 = 9->2->1 and l2 = 9-> 8
add the first elements of both list 9 + 9 = 18 put it in the stack
add second element until all the elements are empty and put it in the queue so queue become
18, 10,1
then dequeue up element if greater than 10, then remove 10 and add 1 for the next element
so it become 8, (10+1) = 11-10 =1 , 1+1 = 2 and then put it a new list become 8->1->2
now reverse the list = 2->1->8
hope this is clear

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

With the reversing->adding->reversing we need 5 iterations (i.e., revering two list, adding two list and reversing the resultant list).

Instead why not add the lists in the forward direction creating add-list and carry-list, then add the add-list and carry-list to get the final list. (Note: we need to iterate both the list to find the respective lengths first).

lets try this way Sum: 9999 + 9999
Add-list is 088888 and the carry list is 111110 and adding this list will give us 199998.

Complicity is 4 iterations (2 iterations to identify the length of the lists and 2 iterations for adding).

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

Here's my tail recursive version, which doesn't require first finding the lengths, first reversing, converting the lists to numbers, or using additional data structures such as Stack etc. It won't handle the case of overflow, so I might be solving an easier version of this problem.

The approach is to use 2 additional parameters (num & num2) to keep track of the current values we have seen for both lists. Code should be self-explanatory enough...

``````static int sum(Node n, Node n2, int num, int num2) {
if(n == null && n2 == null)
return num+num2;
else if(n == null)
return sum(null, n2.next, num, 10*num2 + n2.value);
else if(n2 == null)
return sum(n.next, null, 10*num + n.value, num2);
else return sum(n.next, n2.next, 10*num + n.value, 10*num2 + n2.value);
}``````

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

int addLists (node* list1, node* list2)
{
while (list1->next != NULL && list2->next!= NULL)
{
if(list1->next != NULL) list1 = list1->next;
if(list2->next != NULL) list2 = list2->next;
}

return final;
}

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

This problem can be solved using stack.
Step1: Insert all the elements in the list1 into a stack say s1
Step2: Insert all the elements in the list2 into a stack say s2
Step3:
int val1,val2,carry=0;
while(!s1.empty() || !s2.empty())
{
val1=0;
val2=0;
if(!s1.empty())
{
val1=s1.top();
s1.pop();
}
if(!s2.empty())
{
val2=s2.top();
s2.pop();
}
if(val1+val2+carry> 10)
{
carry=1;
insertintoll((val1+val2+carry)-10);
}
else
{
carry=0;
insertintoll((val1+val2+carry));
}
}

Note: insertintoll() function inserts the value to the front of the new linked list

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

My Generation

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

Here is the code from k2code.blogspot.in/2009/12/write-program-to-add-two-long-positive.html:

``````node *long_add(mynode *h1, mynode *h2, mynode *h3)    //h3 = h2+h1
{
node *c, *c1, *c2;
int sum, carry, digit;

carry = 0;
c1 = h1->next;
c2 = h2->next;

while(c1 != h1 && c2 != h2)
{
sum   = c1->value + c2->value + carry;
digit = sum % 10;
carry = sum / 10;

h3 = insertNode(digit, h3);

c1 = c1->next;
c2 = c2->next;
}

if(c1 != h1)
{
c = c1;
h = h1;
}
else
{
c = c2;
h = h2;
}

while(c != h)
{
sum   = c->value + carry;
digit = sum % 10;
carry = sum / 10;
h3 = insertNode(digit, h3);
c = c->next;
}

if(carry==1)
{
h3 = insertNode(carry, h3);
}

return(h3);
}``````

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

Deque<Integer> n1St = new ArrayDeque<Integer>();
Deque<Integer> n2St = new ArrayDeque<Integer>();
//Stack<Integer> st = new Stack<Integer>(); We resort to using ArrayDeque as it is faster than Stack
//Why is ArrayDeque faster than Stack ?
//ArrayDeque is extended from ArrayList whereas Stack is from Vector
//ArrayList is not a synchronized call & hence when we are not working with multi-threaded program, why
//take a perfromance hit by using vector, i.e., Stack

while(t != null){
n1St.push(t.val);
t = t.next;
}

t = num2;
while(t != null){
n2St.push(t.val);
t = t.next;
}

int carry = 0;
int sum = 0;
nd.val = 0;
nd.next = null;
while (!n1St.isEmpty() || !n2St.isEmpty() || (carry != 0)){
if (!n1St.isEmpty())
sum += n1St.pop();
if (!n2St.isEmpty())
sum += n2St.pop();
sum += carry;
carry = sum / 10;
sum = sum % 10;

if (next == null){
next = nd;
} else {
nd.next = next;
next = nd;
}
nd.val = sum;
sum = 0;
}

}

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

Simpler recursive implementation:

``````private static LinkedList<int> AddNumbers(LinkedListNode<int> firstNumNode, LinkedListNode<int> secondNumNode,int carry)
{
//Base Case:
if(null == firstNumNode && null == secondNumNode)
{
//If we have done with the list but we have got Carry value, then create a na new node
//associate it with link list and return
if(carry > 0)
{
return newList;
}
else
//return null otherwise
return null;
}

var tempResult = firstNumNode.Value + secondNumNode.Value + carry;
//Create a Empty List
//Create a new node using the above result assign it to the List.
var newNode = new LinkedListNode<int>(tempResult % 10);

//Go ove for other nodes
if(null != list && null != list.First)
{
while(null != list.First)
{
var node = list.First;
//First remove the node from earlier list and then add it to result
list.Remove(list.First);
//cache it so that next node can be added after "node"
newNode = node;
}
}
return resultList;
}``````

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

``````#include <stdio.h>
#include<stdlib.h>
struct node
{
int data;

};
int create(int val)
{
struct node *newnode;

newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = val;

{

}
else
{
{

}
}
return 0;

}
{
while(temp!=NULL)
{
printf("%d",temp->data);
if(temp!=NULL)
printf("->");
}
printf("\n");
return 0;
}

{
struct node* prev   = NULL;
struct node* current;
struct node* next;
while (current != NULL)
{
prev = current;
current = next;
}
}
{
int c =0,sum=0;
while(temp1!=NULL&&temp2!=NULL)

{

sum= temp1->data+temp2->data+c;
c = sum/10;
sum=sum%10;

struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =sum;
else
{
newnode->data =sum;
}

}
while(temp1==NULL&&temp2!=NULL)
{
sum= temp2->data+c;
c = sum/10;
sum=sum%10;
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =sum;
}
while(temp1!=NULL&&temp2==NULL)
{
sum= temp1->data+c;
c = sum/10;
sum=sum%10;
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =sum;
}
if((temp1==NULL||temp2==NULL)&&c>0)
{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =c;
}
}
int main()
{
int n1,n2,v,i;
printf("enter no ofnodes in 1st list\n");
scanf("%d",&n1);
for(i=0;i<n1;i++)
{
printf("enter val\n");
scanf("%d",&v);
create(v);
}

printf("enter no ofnodes in 2nd list\n");
scanf("%d",&n2);
for(i=0;i<n2;i++)
{
printf("enter val\n");
scanf("%d",&v);
create(v);
}

//code
return 0;``````

}

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

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

The idea is reverse the two link lists. Add node by node and create another link list for each node by node additions. Adjust for any carry over. Now reverse the resultant link list to get the desired link list.

I'll post the code soon.

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

// Find the difference between the given linked list
// assuming its d(suppose 1st linked list is larger)
Node * temp1 = first1;// For first Linked List
Node *temp2 = first 2 ;//For second Linked List
for (int i = 0; i< d; i++)
temp1 = temp->next;
// Now start adding data and keep it in single Node from the left to right side
while( Temp1 != null)
{temp1->data += temp2->data;
temp1= temp1->next;
temp2 = temp2 -> next;
}
//Now start from first node of first list and check if any node data is greater than 10 then just add 1 to the left node of this node and subtract 10 from that.Repeat till all the data of linked list is less than 10
//boundary condition if first data i s greater than 10 we need to create a separate node and link it to first and make this node as first

while (true)
{
int flag = false;
if (first->data > 10)
{
// create new node
Node newnode = malloc (sizeof(node))
newnode->data = 1;
first->data -= 10;
newnode->next = first;
first = newnode;

flag = true;
}

temp1= first;
temp2 = first->next;
while(temp2 != null)
{
if(temp2->data >= 10)
{
temp2->data = temp2->data-10;
temp->data = temp1->data+1;
temp1= temp1->next;
temp2=temp2->next;
flag = true;
}
if(flag == false)
break;
}

}

{

}

Comment hidden because of low score. Click to expand.
0

two loops.. ooh gush this is really over-engineered solution:
this can be done in a single loop: just go through the lists keeping a carry flag

Comment hidden because of low score. Click to expand.
0

How do you plan to get the carry from the least significant digit to the most significant digit in a single loop?

example: 112+888

Other than the least significant digit, none of the digits themselves generate a carry. They only generate a carry once the least significant digit is calculated and the carry moves towards the left. That's why I used recursion above. But I agree with you about nested loops. They are unnecessary, the complexity shouldn't be greater than O(n).

Comment hidden because of low score. Click to expand.
0

aah got you.. I overlooked that the numbers are originally stored in a twisted way, from most to least significant digit, while naturally it should be the other way around

Comment hidden because of low score. Click to expand.
0

so can anyone give a final solution using a single loop with time complexity O(n)

Comment hidden because of low score. Click to expand.
0

I think just keep carry flag is not enough. If there are several consecutive 9s just before the current digit, then one carry should lead to change all the digits which containing 9 and one more before the consecutive 9s. Using a queue will be a good solution for me...I dont know why ppl dont like this method...

Comment hidden because of low score. Click to expand.
0

I am not sure what you're taking about..
if the nos are stored in a normal way, i.e., from least to most significant digit, then the addition can be done using the following loop:

``````int c = 0;
for(i = 0; i < n; i++) {
z[i] = x[i] + y[i] + c;
c = (z[i] >= 10);
if(c == 1)
z[i] -= 10;
}``````

Comment hidden because of low score. Click to expand.
0

keep the track of previous node of temp1.. if sum is greater than 10 then add the carry to previous node data and move previous node by next
.
while( Temp1 != null)
{temp1->data += temp2->data;
if (temp1->data > 10)
{
temp1->data = temp1->data %10;
prev->data = prev->data+1;
}
temp1= temp1->next;
temp2 = temp2 -> next;
prev= prev->next;

Comment hidden because of low score. Click to expand.
0

keep the track of previous node of temp1.. if sum is greater than 10 then add the carry to previous node data and move previous node by next
.
while( Temp1 != null)
{temp1->data += temp2->data;
if (temp1->data > 10)
{
temp1->data = temp1->data %10;
prev->data = prev->data+1;
}
temp1= temp1->next;
temp2 = temp2 -> next;
prev= prev->next;

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

How about starting at the head of the list and pushing the numbers in a stack as we read them.
When end of list reached, pop out numbers from the stack and multiple them with increasing powers of 10 and keep adding them to the result.

Comment hidden because of low score. Click to expand.
0

I think the problem is 1. the number may be too big so that we prefer list to store it. 2. solve it in one pass.(adding to stack is like reversing the list)

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

Set old number as 0, new data from link list
Sum = old number* 10 + link list number
old number = sum
}

traver

Comment hidden because of low score. Click to expand.
0

oops got lot of typo mistakes

int sum = 0;
while(node != null)
{
sum = sum*10 + node->value;
node = node->next;
}

I hope it is more clear now

Comment hidden because of low score. Click to expand.
-2
of 2 vote

if the question means it should be finished in one pass(no turning back), I think the point is how to take care of '9', if it's 1999, you should keep all the four digits and when the summation of next digit is 10, your current result should be be 20000.

In my opinion, after determine which list is longer and their length difference, we can keep add corresponding digits one by one from the front to rear. In the procedure, we can use a Queue to store the node pointer of all the previous nodes we need to keep tracking. If the current digit is not 9, we can give up all the previous tracked nodes in the Queue.
The rule:
If current->value==9: Queue.enqueue(9)
if current->value>9: while(!Queue.isEmpty): Queue.dequeue()->value+1 //add more necessary code to take care of carry
Queue.enqueue(current->value%10)
if current->value<9: while(!Queue.isEmpty): Queue.dequeue()
Queue.enqueue(current->value)

Comment hidden because of low score. Click to expand.
-2
of 2 vote

List l3 =new List();
if(l1 == Null && l2 == Null){
l3=null;
}
while(l1.next != Null && l2.next!= null){
l3.data = l1.data+ l2.data;
l3= l3.next;
}
if(l1.next){
l3.data = l1.data;
l3.next = l1.next;
}
else{
l3.data = l2.data;
l3.next = l2.next;
}

return l3;

}

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.

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