Amazon Interview Question for SDE-2s


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) {
            return head1 == null? head2: head1;
        }

        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;

    }

- aonecoding April 02, 2017 | Flag Reply
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!

- Varun April 03, 2017 | Flag Reply
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.

- Petisnnake April 12, 2017 | Flag Reply
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;
		
		int carry = addLinkedList(l2_1, h, 0);
		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;
		
		carry = addLinkedList(l1.next, l2.next, 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));
				l1.val = toAdd;
			}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;
	}

}

- Sudip April 01, 2017 | Flag Reply
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
} // _add()

// 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
} // addLists()

// 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:         ")
addLists(first,second).print()

- wrleeii April 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package main.resources;

import java.util.LinkedList;

public class LinkedListExample
{

public static void main(String args[]){
LinkedList<Integer> linkedList1 = new LinkedList<Integer> ();
linkedList1.addFirst(6);
linkedList1.add(8);
linkedList1.add(3);
linkedList1.add(9);
linkedList1.add(9);

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

LinkedList<Integer> linkedList2 = new LinkedList<Integer> ();
linkedList2.addFirst(8);
linkedList2.add(9);
linkedList2.add(8);
linkedList2.add(3);
linkedList2.add(9);

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

LinkedList<Integer> sumList = AddLists(linkedList1, linkedList2);

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



}

private static LinkedList<Integer> AddLists(LinkedList<Integer> linkedList1, LinkedList<Integer> linkedList2)

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

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

LinkedList<Integer> sumList = linkedList1;

int carryOver = 0;
int lastCarry = 0;
for (int i= maxSize; i > 0; i--)
{
int j= i-1;
int sum = linkedList1.get(j) + linkedList2.get(j);
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 )
{
sumList.addFirst(lastCarry);
}


}
return sumList;
}

- curlyhairLily April 05, 2017 | Flag Reply
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 ;
}
return Reverse(Head);
}
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;
}

}
}

- mohamadreza.shakouri April 11, 2017 | Flag Reply
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));
}

- John4jobs April 13, 2017 | Flag Reply
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;
}

- John4jobs April 13, 2017 | Flag Reply
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 wholeSize = Math.Max(LengthOfLinkedList(one), LengthOfLinkedList(sec));
            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;
                result.AddFirst(sum);
            }


        }

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

        public int LengthOfLinkedList(LinkedListNode<int> list)
        {
            if (list == null) return 0;
            return 1 + LengthOfLinkedList(list.Next);
        }

- maksymas April 16, 2017 | Flag Reply
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;


namespace Nizar.Solutions.LinkedList
{

	public class LinkedList
	{
		public static void Main(string[] args)
		{
			var left=CreateList(new int[]{1,2,3,7});
			var right=CreateList(new int[]{2,9});
			var addedList=Add(left,right);
			Console.Write("First List=");
			PrintList(left);
			Console.Write("Secod List=");
			PrintList(right);
			Console.Write("Added List=");
			PrintList(addedList);
			Console.ReadLine();
		}
		
		
		static Node Add(Node left,Node right)
		{
				Node leftBeg=left;
				Node leftEnd=left;
				
				Node rightBeg=right;
				Node rightEnd=right;
				
				Node resultHead=null;
				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;
						
						if(resultHead==null)
						{
							resultHead=temp;
							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;
						
										
						if(resultHead==null)
							resultHead=temp;
						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;
					
					if(resultHead==null)
					{
						resultHead=temp;
					}
					else
						prevNode.Next=temp;
					
					prevNode=temp;
							
					leftBeg=leftBeg.Next;
					rightBeg=rightBeg.Next;
				}
				
				
				var head=Reverse(resultHead);
				
				var iterator=head;
				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;
				}
							
				return Reverse(head);
				
		}
		
		
		static Node Reverse(Node head)
		{
			if(head==null)
				return head;
			
			var prevNode=head;
			var currentNode=head.Next;
			
			while(currentNode!=null)
			{
				var temp=currentNode.Next;
				currentNode.Next=prevNode;
				prevNode=currentNode;
				currentNode=temp;
			}
			
			head.Next=null;
			
			return prevNode;
		}
		
		
		
		static Node CreateList(int[] listItems)
		{
			Node head=null;
			Node currentNode=null;
			
			foreach(var item in listItems)
			{
				var temp=new Node();
				temp.data=item;
				if(head==null)
				{
					head=temp;					
				}
				
				if(currentNode==null)
					currentNode=head;
				else
				{
					currentNode.Next=temp;
					currentNode=temp;
				}
				
			}
			
			return head;
		}
		
		
		static void PrintList(Node head)
		{
			var currentNode=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;
	}
}

- Nizar Mankulangara April 25, 2017 | Flag Reply
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;
}

- John Zhang May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public LinkedList<Integer> addList(LinkedList<Integer> l1, LinkedList<Integer> l2) {
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);
LinkedList<Integer> res = new LinkedList<Integer>();
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;
}

- Ashish Shanbhogue May 04, 2017 | 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