Amazon Interview Question SDE1s
Team: web service
Country: United States
Can we use a linked list to represents digits of the integer? If yes then this problem can be transformed into sum of two linked lists. If we want to make this more efficient then instead of storing one digit per node we can store n bytes per node. We just need to make sure that the sum and carry are propagated properly.
Assumption for 1 digit per node
Time O(n)
SpaceO(1)
This will work for different length lists as well
public class SumTwoList2 {
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// traverse through the list to find the size
private int size(Node head) {
Node temp = head;
int len = 0;
while (temp != null) {
len++;
temp = temp.next;
}
return len;
}
public Node addLists(Node head1, Node head2) {
// if either of the lists are empty then take appropriate action
if (head1 == null && head2 == null) {
return null;
} else if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
Node result = null;
int l1 = size(head1);
int l2 = size(head2);
int len = 0;
int i;
// start pushing the bigger list items on the stack
if (l1 > l2) {
len = l2;
for (i = 0; i < l1 - l2; i++) {
Node n = new Node(head1.data);
head1 = head1.next;
n.next = result;
result = n;
}
} else if (l1 < l2) {
len = l1;
for (i = 0; i < l2 - l1; i++) {
Node n = new Node(head2.data);
head2 = head2.next;
n.next = result;
result = n;
}
}
// Now both lists are same length
for (i = 0; i < len; i++) {
Node n = new Node(head1.data + head2.data);
head1 = head1.next;
head2 = head2.next;
n.next = result;
result = n;
}
int sum = 0, carry = 0;
Node ptr = result;
// adjust the carry and forward it to next node
while(ptr != null) {
sum = ptr.data;
ptr.data = sum%10 + carry;
carry = sum / 10;
ptr = ptr.next;
}
// if a carry exists we need another node to put this
if (carry != 0) {
Node n = new Node(carry);
n.next = result;
result = n;
}
reverse(result);
return result;
}
public void reverse(Node head) {
if(head == null || head.next == null) {
return;
}
Node p = head;
Node q = head.next;
Node r = null;
while(q != null) {
r = q.next;
q.next = p;
p = q;
q = r;
}
head.next = null;
head = p;
}
}
If implementing in C++, take inputs as strings and use const_reverse_iterator to compute sum and carry of each digits.
string
large_add(const string &num1, const string &num2)
{
int sum = 0, carry = 0;
string result;
string::const_reverse_iterator itr1 = num1.rbegin();
string::const_reverse_iterator itr1_end = num1.rend();
string::const_reverse_iterator itr2 = num2.rbegin();
string::const_reverse_iterator itr2_end = num2.rend();
while (true) {
// iterate both the numbers
if (itr1 != itr1_end && itr2 != itr2_end) {
sum = (*itr1 - '0') + (*itr2 - '0') + carry;
++itr1; ++itr2;
} else if (itr1 != itr1_end && itr2 == itr2_end) {
sum = (*itr1 - '0') + carry;
++itr1;
} else if (itr1 == itr1_end && itr2 != itr2_end) {
sum = (*itr2 - '0') + carry;
++itr2;
} else {
break;
}
result.insert(0, 1, (sum%10) + '0');
carry = sum/10;
}
// is carry left
if (carry) {
result.insert(0, 1, carry+'0');
}
return result;
}
BASE = 100 # Can be any int > 1
class BigPosInt(object):
def __init__(self, v=0):
self.little_endian = []
while v >= BASE:
self.little_endian.append(v % BASE)
v /= BASE
else:
if v > 0:
self.little_endian.append(v)
def Add(self, other):
shared_len = min(len(self.little_endian), len(other.little_endian))
result = BigPosInt()
carry_over = 0
for i in xrange(shared_len):
v = self.little_endian[i] + other.little_endian[i] + carry_over
result.little_endian.append(v % BASE)
carry_over = v / BASE
if len(self.little_endian) > shared_len:
for i in xrange(shared_len, len(self.little_endian)):
v = self.little_endian[i] + carry_over
result.little_endian.append(v % BASE)
carry_over = v / BASE
elif len(other.little_endian) > shared_len:
for i in xrange(shared_len, len(other.little_endian)):
v = other.little_endian[i] + carry_over
result.little_endian.append(v % BASE)
carry_over = v / BASE
if carry_over > 0:
result.little_endian.append(carry_over)
return result
def Print(self):
total = 0
for i, v in enumerate(self.little_endian):
total += (v * (BASE ** i))
print self.little_endian, total
x = BigPosInt(99)
x.Print()
y = BigPosInt(1)
y.Print()
z = BigPosInt(9999)
z.Print()
s1 = x.Add(y)
s1.Print()
s2 = z.Add(y)
s2.Print()
s3 = y.Add(z)
s3.Print()
This should solve the problem:
- nitin.sharma4959 May 02, 2013#include <stdio.h> #include <stdlib.h> #include <string.h> void main() { char *number1 = NULL, *number2 = NULL, *result = NULL; int max_no_of_digit = 0, carry = 0, i, add = 0, len_num1 = 0, len_num2 = 0, j, index; char ch; printf("\nPlease enter max no of digit in a number"); scanf("%d",&max_no_of_digit); number1 = (char*) calloc(max_no_of_digit,sizeof(char)); number2 = (char*) calloc(max_no_of_digit,sizeof(char)); result = (char*) calloc(max_no_of_digit+1,sizeof(char)); printf("\nPlease enter first number:"); scanf("%s",number1); printf("\nPlease enter second number:"); scanf("%s",number2); len_num1 = strlen(number1); len_num2 = strlen(number2); printf("\nYour Answer is:: "); index = len_num1 >= len_num2 ? len_num1:len_num2; result[index + 1] = '\0'; for(i = len_num1-1, j = len_num2-1;; i--, j--) { index = i >= j ? i:j; if(i>=0 && j>=0) add = carry + number1[i] + number2[j] - 2*'0'; else if(i>=0) add = carry + number1[i] - '0'; else if(j>=0) add = carry + number2[j] - '0'; else { if(carry == 1) result[index+1] = carry + '0'; break; } index = i >= j ? i:j; carry = add/10; result[index+1] = (add%10)+48; } printf("%s\n",result); }