Amazon Interview Question SDE-2s
Country: India
Interview Type: Written Test
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;
}
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!
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.
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;
}
}
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()
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;
}
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;
}
}
}
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));
}
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;
}
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);
}
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;
}
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;
}
Solution that uses constant space !
- Nizar Mankulangara April 25, 2017/* 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; } }