## Amazon Interview Question for SDE-2s

• 1
of 1 vote

Country: India
Interview Type: Written Test

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

Looking for interview questions sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).

We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding,
algorithms,
system design
and mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work.

Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.

Welcome to email us with any questions. Thanks for reading.

Solution:
Iterate through the two lists twice. First time get the difference in length. Second time get the sum at every digit (allow a node to have 2 digits). And then iterate through the new result array once to deal with the carry.

``````public ListNode add(ListNode head1, ListNode head2) {

if(head1 == null || head2 == null) {
}

int diff = 0; //get the difference in lengths of the two lists

ListNode p1 = head1, p2 = head2;
while(p1 != null && p2 != null) {
p1 = p1.next;
p2 = p2.next;
}

ListNode longer = p1 == null? head2: head1;
ListNode shorter = p1 == null? head1: head2;

while(p1 != null) {
p1 = p1.next;
diff++;
}

while(p2 != null) {
p2 = p2.next;
diff++;
}

ListNode dump = new ListNode(0);  //create a dummy head for the result list
ListNode curr= dump;

while(diff > 0) {   //create the longer part of the longer list
diff--;
curr.next = new ListNode(longer.val);
longer = longer.next;
curr = curr.next;
}

while(longer != null) { //add the two lists
curr.next = new ListNode(longer.val + shorter.val);
curr = curr.next;
longer = longer.next;
shorter = shorter.next;
}

curr = dump;
ListNode carry = dump;
while(curr != null) {       //carry always points at the number smaller than 9
if(curr.val < 9) {      //when a carry is found at current node, add 1 to carry and change anything after carry and before curr to 0
carry = curr;
} else if(curr.val > 9){
carry.val++;
carry = carry.next;
while(carry != curr) {
carry.val = 0;
carry = carry.next;
}
curr.val %= 10;
}
curr = curr.next;
}

return dump.val == 0 ? dump.next: dump;

}``````

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

There's no mention if we cannot use extra memory, so its easier to use stack.
Scan list 1 and push to stack 1.
Scan list 2 and put to stack 2.

Now, start popping from stk1 and stk2 , add the numbers, save carry if any, and store result in a list.

Once the stacks are completely popped, the new list is the answer!

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

The challenge here is to do it using constant memory.
The time complexity is theta of n+m so we cant do anything there.
All the solutions you guys posted are garbage.

1. Iterate over lists to get their length.
2. Add each corresponding digit from left to right disregarding the carry. Lets call this S.
3. Add each digit and only consider the carry. 1 if it produces a carry 0 if not. Call this C.
4. Return S+C*10

1 2 3 7
2 9

Produces S=1256 and C=1.

O(n+m) time O(1) space.

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

``````public class AddTwoLinkedList {

public static void main(String[] args) {
LL l2_4 = new LL(7, null);
LL l2_3 = new LL(3, l2_4);
LL l2_2 = new LL(2, l2_3);
LL l2_1 = new LL(1, l2_2);

LL l1_2 = new LL(9, null);
LL l1_1 = new LL(2, l1_2);

int s1 = 0;
LL l1 = l1_1;
while(l1 != null){
l1 = l1.next;
s1++;
}
int s2 = 0;
LL l2 = l2_1;
while(l2 != null){
l2 = l2.next;
s2++;
}
int c = s2-s1-1;
LL prev = new LL(0, null);
LL h = prev;
while(c > 0){
LL l = new LL(0, null);
prev.next = l;
prev = l;
c--;
}
prev.next = l1_1;

LL lh = l2_1;
if(carry > 0){
lh = new LL(carry, l2_1);
}

while(lh != null){
System.out.print(lh.val + " ");
lh = lh.next;
}
}

static int addLinkedList(LL l1, LL l2, int carry){
if(l1 == null && l2 == null) return carry;

if(l1 != null && l2 != null){
int sum = l1.val + l2.val + carry;
if(sum > 9){
String str = String.valueOf(sum);
int toAdd = Integer.parseInt(str.substring(1,str.length()));
carry = Integer.parseInt(str.substring(0,1));
}else{
l1.val = sum;
carry = 0;
}
}
return carry;
}

}
class LL{
int val;
LL next;
public LL(int val, LL next){
this.val = val;
this.next = next;
}``````

}

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

We must traverse both lists from their ends toward their beginnings. We can traverse one of the lists starting from the end via a recursive function, but it is a challenge to coordinate two different length lists that way. So we can traverse the other list first, pushing its elements into a stack. Then, as we unwind the recursion of the one list, we pop the elements of the converted list. In case the recursed list is shorter than the "stacked" list, we pop the rest of the elements, creating prefixing the "sum" with the elements of the stack that hadn't been "added". No counting necessary, O(m+n) time

In raw JavaScript, with a little NodeJS-ism for output:

``````// A Linked-list class
function LL(data, next) {
// console.log("insert "+data)
this.data = data;
this.next = next;
}
LL.prototype.print = function () {
process.stdout.write(this.data.toString())
if (this.next) {
process.stdout.write('-> ')
this.next.print()
}
else
process.stdout.write('\n')
}

// Recursive function to add a "stack" to a Linked-list
function _add(stack, list) {
let sum;
if (! list.next ) {
sum = new LL((stack.length == 0 ? 0 : stack.pop()) + list.data, null)
}
else {
sum = _add(stack, list.next)
sum = new LL((stack.length == 0 ? 0 : stack.pop()) + list.data,
sum)
if (sum.next.data > 9) {
sum.next.data -= 10
sum.data += 1
}
}
return sum

// This is the function solution to the exercise:
function addLists( L1, L2 ) {
let stack=[];						// Tempoary data struct
for (let i=L1; i; i=i.next)	// Fill the stack w/one list
stack.push(i.data)

let sum = _add(stack, L2)		// Add the revised list to the other list
let carry = ( sum.data > 9 )
if (carry) sum.data -= 10;		// If most signifant element overflowed...

while (stack.length)	{			// While there are list elements left
sum = new LL(stack.pop(), sum)
if (carry) {					// Make sure handle the carry-over
sum.data += 1;				// is added to the next digit
carry = false;				// This only needs to be done once
}
}
if (carry) {						// Make sure carry-over was handled
sum = new LL(1, sum)			// adding a node, since no stack elements
}										// were able to absorb it

return sum;							// Return final list

// Create test Linked-lists
var first	= new LL( 1, new LL( 2, new LL( 3, new LL(7))))
var second	= new LL( 2, new LL (9, null))

// Make sure they're constructed correctly
process.stdout.write("First list:  ")
first.print()
process.stdout.write("Second list: ")
second.print()
process.stdout.write("Sum:         ")

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

package main.resources;

{

public static void main(String args[]){

System.out.println("Linked List 1 Content: " + linkedList1);

System.out.println("Linked List 2 Content: " + linkedList2);

System.out.println("Linked List 1+2 Content: " + sumList);

}

{
int size1 = linkedList1.size();
int maxSize = size1;
int size2 = linkedList2.size();
if ( size2 > maxSize)
{
maxSize = size2;
}
else if ( size1 > size2)
{

}
System.out.println("Linked List 1 Content: " + linkedList1);
System.out.println("Linked List 2 Content: " + linkedList2);

int carryOver = 0;
int lastCarry = 0;
for (int i= maxSize; i > 0; i--)
{
int j= i-1;
if (sum >= 10 )
{
carryOver = 1;
sum = sum - 10;
}
else
{
carryOver = 0;

}
if ( i < maxSize)
{
sum = sum + lastCarry;
}
sumList.set(j, sum);
lastCarry = carryOver;
if ( j == 0 && lastCarry != 0 )
{
}

}
return sumList;
}

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

using System;

public class Program
{
public static void Main()
{
Node n1 = new Node(1);
Node n2 = new Node(7);
//Node n3 = new Node(1);

//n1.next = n2;
//n2.next = n3;

Node n4 = new Node(8);
Node n5 = new Node(7);
Node n6 = new Node(0);

n4.next = n5;
n5.next = n6;
Node cursor = Addition(n1 , n4);
while(cursor != null)
{
Console.Write(cursor.data);
cursor = cursor.next;
}
}

public static Node Addition (Node number1 , Node number2)
{
Node num1 = Reverse(number1);
Node num2 = Reverse(number2);
Node Head = new Node(0);
Node result = Head;
int temp = 0;
int carry = 0 ;
while (num1 != null || num2 !=null)
{
if (num1 == null)
{
num1 = new Node(0);
}
if (num2 == null)
{
num2 = new Node(0);
}
temp = num1.data + num2.data + carry;
carry = 0;
if (temp > 9)
{
result.data = temp % 10 ;
carry = temp / 10 ;
}
else
{
result.data = temp;
}
if (result.next == null)
{
result.next = new Node(0);
}
result = result.next;
num1 = num1.next;
num2 = num2.next;
}
if (carry > 0)
{
result.data = carry ;
}
}
public static Node Reverse (Node head)
{
Node cur = head;
Node prev = null;
Node next = null;

while (cur != null)
{
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
public class Node{

public Node prev;
public Node next;
public int data ;
public Node (int d)
{
this.data = d;
}

}
}

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

Reverse both linked lists and traverse from end maintain carry

ListNode *reverse(ListNode *head) {
Node *curr = head;
Node *temp, *result;
temp = result = NULL;

while (curr) {
temp = curr->next;
curr->next = result;
result = curr;
curr = temp;
}

return result;
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
Node *tf = reverse(l1);
Node *ts = reverse(l2);
Node dummy;
Node *result = &dummy;
int carry =0,sum=0;

while (tf || ts || carry) {
sum = carry;
if (tf) {
sum += tf->data;
tf = tf->next;
}
if (ts) {
sum += ts->data;
ts = ts->next;
}
result->next = new Node(sum % 10);
carry = sum/10;
result = result->next;
}
return (reverse(dummy.next));
}

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

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
Node *tf = reverse(l1);
Node *ts = reverse(l2);
Node dummy;
Node *result = &dummy;
int carry =0,sum=0;

while (tf || ts || carry) {
sum = carry;
if (tf) {
sum += tf->data;
tf = tf->next;
}
if (ts) {
sum += ts->data;
ts = ts->next;
}
result->next = new Node(sum % 10);
carry = sum/10;
result = result->next;
}
return (reverse(dummy.next));
}

ListNode *reverse(ListNode *head) {
Node *curr = head;
Node *temp, *result;
temp = result = NULL;

while (curr) {
temp = curr->next;
curr->next = result;
result = curr;
curr = temp;
}

return result;
}

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

Simple and elegant c# - O(N) time and O(1) space

``````public void Adding2LinkedList(LinkedListNode<int> one = null, LinkedListNode<int> sec = null)
{
int sum = 0;
int carry = 0;
var result = new LinkedList<int>();
for (int i = 0; i < wholeSize; i++)
{
count = 0;
var elemOne = FindTheKthLastElement(one, i);
count = 0;
var elemSec = FindTheKthLastElement(sec, i);
sum = (elemOne + elemSec + carry) % 10;
carry = (elemOne + elemSec + carry) / 10;
}

}

public int FindTheKthLastElement(LinkedListNode<int> list, int k)
{
int num = 0;
if (list == null) return num;

num = FindTheKthLastElement(list.Next, k);
if (count++ == k)
return list.Value;
return num;
}

{
if (list == null) return 0;
return 1 + LengthOfLinkedList(list.Next);
}``````

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

Solution that uses constant space !

``````/*

Implemented Solution

1. first simply add the two list
a. add the elements from bigger list
b. add the corresponding element (just add and dont worry about carry)
2. Reverse the added list
3. Traverse through the list from beginning to end and adjust those elmeents which are >9 and add the corresponding carry to next node
4. Reverse the result list
*/

using System;

{

{
public static void Main(string[] args)
{
var left=CreateList(new int[]{1,2,3,7});
var right=CreateList(new int[]{2,9});
Console.Write("First List=");
PrintList(left);
Console.Write("Secod List=");
PrintList(right);
}

static Node Add(Node left,Node right)
{
Node leftBeg=left;
Node leftEnd=left;

Node rightBeg=right;
Node rightEnd=right;

Node prevNode=null;

while(leftEnd!=null && rightEnd!=null)
{
leftEnd=leftEnd.Next;
rightEnd=rightEnd.Next;
}

if(leftEnd==null)
{
while(rightEnd!=null)
{
var temp=new Node();
temp.data=rightBeg.data;

{
prevNode=temp;
}
else
prevNode.Next=temp;

rightEnd=rightEnd.Next;
rightBeg=rightBeg.Next;
}
}

if(rightEnd==null)
{
while(leftEnd!=null)
{
var temp=new Node();
temp.data=leftBeg.data;

else
prevNode.Next=temp;

prevNode=temp;

leftEnd=leftEnd.Next;
leftBeg=leftBeg.Next;
}
}

while(leftBeg!=null && rightBeg!=null)
{

var temp=new Node();
temp.data=leftBeg.data+rightBeg.data;

{
}
else
prevNode.Next=temp;

prevNode=temp;

leftBeg=leftBeg.Next;
rightBeg=rightBeg.Next;
}

var carry=0;

while(iterator!=null)
{
var result=iterator.data+carry;
if(result>9)
{
result=result%10;
carry=1;
}
else
carry=0;

iterator.data=result;

if(iterator.Next==null && carry==1)
{
var temp=new Node();
temp.data=1;
iterator.Next=temp;
iterator=temp;
}

iterator=iterator.Next;
}

}

static Node Reverse(Node head)
{

while(currentNode!=null)
{
var temp=currentNode.Next;
currentNode.Next=prevNode;
prevNode=currentNode;
currentNode=temp;
}

return prevNode;
}

static Node CreateList(int[] listItems)
{
Node currentNode=null;

foreach(var item in listItems)
{
var temp=new Node();
temp.data=item;
{
}

if(currentNode==null)
else
{
currentNode.Next=temp;
currentNode=temp;
}

}

}

static void PrintList(Node head)
{
while(currentNode!=null)
{
Console.Write(currentNode.data);
currentNode=currentNode.Next;
Console.Write(currentNode==null?"":"->");
}

Console.WriteLine("");
}

}

class Node
{
public int data;
public Node Next;
}
}``````

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

My Approach: recursion of two linkedlists to add, which it too hard to coordinate and need caller, I applied two stacks solution to do everything in one subroutine , easy to read
public String addLinkedList(Node l1, Node l2) {
if (l1==null && l2==null) return "";
Node n1 = l1;
Node n2 = l2;
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while (n1!=null) {
stack1.push(n1);
n1 = n1.next;
}
while (n2!=null) {
stack2.push(n2);
n2 = n2.next;
}
String result="";
int cary=0;
String arrow ="";
while (!stack1.isEmpty() || !stack2.isEmpty()) {
int v1 =0, v2=0;

if (!stack1.isEmpty()) {
v1 = stack1.pop().data;

}
if (!stack2.isEmpty()) {
v2= stack2.pop().data;

}
int dsum = v1+v2+cary;
int digit = dsum%10;
cary = dsum/10;
System.out.println("digit="+digit);
result = String.valueOf(digit)+arrow+result;
arrow = "->";
}
if (cary>0) {
result = String.valueOf(cary)+arrow+result;
}

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

Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
Stack<Integer> sumSt = new Stack<Integer>();
int carry = 0;
for (Integer i : l1)
s1.push(i);
for (Integer i : l2)
s2.push(i);
while (!s1.isEmpty() || !s2.isEmpty()) {
int v1 = 0, v2 = 0, sum = 0;
if (!s1.isEmpty())
v1 = s1.pop();
if (!s2.isEmpty())
v1 = s2.pop();
sum = v1 + v2 + carry;
carry = sum / 10;
sum = sum % 10;
sumSt.push(sum);
}
while (!sumSt.empty())
res.push(sumSt.pop());
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.