## Amazon Interview Question for SDE1s

• 0

Country: United States

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

Assuming the LinkedList head starts at the least significant digit for both a and b:

``````public ListNode addLinkedListNodes(ListNode a, ListNode b) {
ListNode resultP = null;
ListNode result = resultP;
int carry = 0;

while (a != null || b!= null)  {
if (resultP == null) {
resultP = new ListNode();
} else {
resultP.next = new ListNode();
resultP = resultP.next();
}

if (a == null) {
result.value = (b.value + carry) %10;
carry = (b.value + carry) / 10;
b = b.next;
} else if (b == null) {
result.value = (a.value + carry) % 10;
carry = (a.value + carry) / 10;
a = a.next;
} else {
result.value = (a.value + b.value + carry) % 10;
carry = (a.value + b.value + carry) / 10;
a = a.next;
b = b.next;
}
}

return result;
}``````

Otherwise if the most significant digit is first you could reverse both LinkedLists as the first step.

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

What if there is a carry left after you finish iterating?

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

Can you please explain the importance of resultP and result specifically ?

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

Thanks Plyush, I should have run through some testcases.

edit: after the while loop

``````if (carry > 0) {
resultP.next = new ListNode();
resultP.next.value = carry;
}``````

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

I really didn't understand this part of code.
if (resultP == null) {
resultP = new ListNode();
} else {
resultP.next = new ListNode();
resultP = resultP.next();
}

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

The point of 'resultP' is it's a pointer (aka reference) to the current ListNode object in the summed linkedlist. As the values are added, 'resultP' points to the most recently summed digit in the resultant linked list. 'result' is used just to keep track of the beginning of the linked list.

The if-else statement is there to create the first node of the result linked list.

Also another error with my code:
'result' should be assigned to 'resultP' in the if block. 'result' always points to the 1st node of the LL that is returned.

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

So this is what ur complete code shld look :

ListNode resultP = null;
ListNode result = resultP;
int carry = 0;

while (a != null || b!= null) {
if (resultP == null) {

resultP = new ListNode();

} else {
resultP.next = new ListNode();
resultP = resultP.next();
}

if (a == null) {
result.value = (b.value + carry) %10;
carry = (b.value + carry) / 10;
b = b.next;
} else if (b == null) {
result.value = (a.value + carry) % 10;
carry = (a.value + carry) / 10;
a = a.next;
} else {
result.value = (a.value + b.value + carry) % 10;
carry = (a.value + b.value + carry) / 10;
a = a.next;
b = b.next;
}
}
if (carry > 0) {
resultP.next = new ListNode();
resultP.next.value = carry;
result=resultP;
}
return result;
}

Correct me If I am worng

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

What if the numbers to be added are 851 and 74. As I understand, the linked list would be represented as follows:

8 -> 5 -> 1 -> 7 -> 4

Is there any additional info provided, like where the second number begins etc? I'm afraid I don't quite understand the Q.

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

It's kind of vague, but I think people are interpreting it as each number is its own linked list. The head of the linked list can be either the most significant digit or the least.
num1 -> 8 -> 5 -> 1
num2 -> 7 -> 4
result -> 9 -> 2 ->5

or num1 -> 1 -> 5 ->8
etc

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

``````package com.java.linkedlist;

public class Node {
int data;
Node next;
public Node(int d)
{
this.data=d;
this.next=null;
}
void appendToTail(int d)
{
Node end=new Node(d);
Node n=this;
while(n.next!=null)
{
n=n.next;
}
n.next=end;

}
Node reverse()
{
if (this == null || this.next == null)
return this;  //empty or just one node in list

Node Second = this.next;

//store third node before we change
Node Third = Second.next;

//Second's next pointer
Second.next = this;  //second now points to head
this.next = null;  //change head pointer to NULL

//only two nodes, which we already reversed
if (Third == null)
return Second;

while (Third != null)
{
Node NextNode = Third.next;

Third.next = Second;

/*  repeat the process, but have to reset
the Second and Third
*/

Second =Third;
Third = NextNode;
}

Node r = Second; //reset the head node
return r;
}
{
Node result;
if(this==null&&num2==null)
return null;
if(this==null)
return num2;
if(num2==null)
return this;
Node num1=this;
int sum=0;
int r=0;
sum=(sum+num1.data+num2.data)%10;
result=new Node(sum);
r=(num1.data+num2.data)/10;
num1=num1.next;
num2=num2.next;
while(num1!=null&& num2!=null)
{
sum=(num1.data+num2.data+r)%10;
result.appendToTail(sum);
r=(num1.data+num2.data+r)/10;
num1=num1.next;
num2=num2.next;
}
while(num1!=null)
{
sum=(r+num1.data)%10;
result.appendToTail(sum);
r=(r+num1.data)/10;
num1=num1.next;
}
while(num2!=null)
{
sum=(r+num2.data)%10;
result.appendToTail(sum);
r=(r+num2.data)/10;
num2=num2.next;
}
return result;
}
public static void main(String args[])
{
/*Numbers to add are 549 and 65*/
Node num1=new Node(5);
num1.appendToTail(4);
num1.appendToTail(9);
Node rev1=num1.reverse();
Node num2=new Node(6);
num2.appendToTail(5);
Node rev2=num2.reverse();
Node resultRev=sum.reverse();
while(resultRev!=null)
{
System.out.print(resultRev.data);
resultRev=resultRev.next;
}
}

}``````

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

Those are not good solutions indeed, too complicated anyways.
Here is my code:

``````public Node add( Node n1, Node n2){
if ( n1 == null || n2 == null ) return null;
int sum = transferListToInt(n1)+transferNodeToInt(n2);
return transferIntToList(sum);
}

private int transferListToInt( Node node ){
if ( node == null ) return 0;
curNode = node;
String res = "";
while ( true ){
res += curNode.getDigit(); // assume getDight returns the digit in node
if ( curNode.next() == null ) break;
curNode = curNode.next();
}
return Integer.parseInt(res);
}

private Node transferIntToList( int num ){
curNode = null;
while ( num != 0 ){ // for now just ignore the negative case
Node newNode = new Node(num%10);
num = num /10;
newNode.next = curNode;
curNode = newNode;
}
return curNode;
}``````

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

Nice, working fine. We can do one small change here to avoid string manipulation.
take res as int variable with 0 as default value and then we can use multipkication to create actual number in place like :

private int transferListToInt( Node node ){
if ( node == null ) return 0;
curNode = node;
int res = 0;
while ( node != null ){
res = (res * 10) + curNode->data;
curNode = curNode -> next;
}
return res;
}

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.