Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
u didnt take care of carrying? what if 1->9->5 + 1->5, u need to turn around and change 1 to be 2, change 0 to be 1
Actually my understand of the problem statement was wrong.
Following code is working for all scenarios, assuming that each node value of the given lists is a 1 digit number.
public static ListNode reverse(ListNode head) {
ListNode previous = null;
ListNode current = head;
ListNode forward;
while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public static ListNode sumOfTheLists(ListNode head1, ListNode head2)
{
if(head1 == null && head2 == null)
{
return null;
}
if(head1 == null && head2 != null)
{
return head2;
}
if(head1 != null && head2 == null)
{
return head1;
}
LinkedList result = new LinkedList();
ListNode rhead1 = reverse(head1);
ListNode rhead2 = reverse(head2);
int temp = 0;
while(rhead1 != null || rhead2 != null)
{
if(rhead1 != null && rhead2 != null)
{
temp += (Integer)rhead1.element+(Integer)rhead2.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
rhead2 = rhead2.next;
}
else
{
if(rhead1 != null)
{
temp += (Integer)rhead1.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
}
if(rhead2 != null)
{
temp += (Integer)rhead2.element;
temp = addDigits(result, temp);
rhead2 = rhead2.next;
}
}
}
if(temp != 0)
{
result.insertLast(temp);
}
return reverse(result.head);
}
private static int addDigits(LinkedList result, int temp) {
if( temp >= 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
return temp;
}
Hi,
Without using linked lists, I can think of following two ways.
1) Convert each list into integer, then sum up the two integer values(list1, list2) and then construct new linked list with that sum.
But this will not work, since sum can overflow.
2) Using two stacks, but here space complexity will become double.
Is there any other approach?
Yes, you are correct.
Below one will work, but I need to refactor
public static ListNode reverse(ListNode head) {
ListNode previous = null;
ListNode current = head;
ListNode forward;
while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public static ListNode sumOfTheLists(ListNode head1, ListNode head2)
{
if(head1 == null && head2 == null)
{
return null;
}
if(head1 == null && head2 != null)
{
return head2;
}
if(head1 != null && head2 == null)
{
return head1;
}
LinkedList result = new LinkedList();
ListNode rhead1 = reverse(head1);
ListNode rhead2 = reverse(head2);
int temp = 0;
while(rhead1 != null || rhead2 != null)
{
if(rhead1 != null && rhead2 != null)
{
temp += (Integer)rhead1.element+(Integer)rhead2.element;
if(temp%10 != 0 || temp == 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
rhead1 = rhead1.next;
rhead2 = rhead2.next;
}
else
{
if(rhead1 != null)
{
temp += (Integer)rhead1.element;
if(temp%10 != 0 || temp == 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
rhead1 = rhead1.next;
}
if(rhead2 != null)
{
temp += (Integer)rhead2.element;
if(temp%10 != 0 || temp == 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
rhead1 = rhead2.next;
}
}
}
return reverse(result.head);
}
This is working in all cases:
public static ListNode reverse(ListNode head) {
ListNode previous = null;
ListNode current = head;
ListNode forward;
while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public static ListNode sumOfTheLists(ListNode head1, ListNode head2)
{
if(head1 == null && head2 == null)
{
return null;
}
if(head1 == null && head2 != null)
{
return head2;
}
if(head1 != null && head2 == null)
{
return head1;
}
LinkedList result = new LinkedList();
ListNode rhead1 = reverse(head1);
ListNode rhead2 = reverse(head2);
int temp = 0;
while(rhead1 != null || rhead2 != null)
{
if(rhead1 != null && rhead2 != null)
{
temp += (Integer)rhead1.element+(Integer)rhead2.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
rhead2 = rhead2.next;
}
else
{
if(rhead1 != null)
{
temp += (Integer)rhead1.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
}
if(rhead2 != null)
{
temp += (Integer)rhead2.element;
temp = addDigits(result, temp);
rhead1 = rhead2.next;
}
}
}
if(temp != 0)
{
result.insertLast(temp);
}
return reverse(result.head);
}
private static int addDigits(LinkedList result, int temp) {
if(temp%10 != 0 || temp == 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
return temp;
}
Sorry for the duplication, this is working for all the scenarios. Time complexity and space complexity is O(max(m,n)).
public static ListNode reverse(ListNode head) {
ListNode previous = null;
ListNode current = head;
ListNode forward;
while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public static ListNode sumOfTheLists(ListNode head1, ListNode head2)
{
if(head1 == null && head2 == null)
{
return null;
}
if(head1 == null && head2 != null)
{
return head2;
}
if(head1 != null && head2 == null)
{
return head1;
}
LinkedList result = new LinkedList();
ListNode rhead1 = reverse(head1);
ListNode rhead2 = reverse(head2);
int temp = 0;
while(rhead1 != null || rhead2 != null)
{
if(rhead1 != null && rhead2 != null)
{
temp += (Integer)rhead1.element+(Integer)rhead2.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
rhead2 = rhead2.next;
}
else
{
if(rhead1 != null)
{
temp += (Integer)rhead1.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
}
if(rhead2 != null)
{
temp += (Integer)rhead2.element;
temp = addDigits(result, temp);
rhead2 = rhead2.next;
}
}
}
if(temp != 0)
{
result.insertLast(temp);
}
return reverse(result.head);
}
private static int addDigits(LinkedList result, int temp) {
if( temp >= 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
return temp;
}
A little bit shorter solution, written in Java
public static LinkedList<Integer> sum(LinkedList<Integer> l1, LinkedList<Integer> l2){
if(l1==null||l2==null)return null;
LinkedList<Integer> result = new LinkedList<Integer>();
int s1=l1.size();
int s2=l2.size();
int shift=s2-s1;
shift=shift<0?-shift:shift;
Iterator<Integer> longer = s2>s1?l2.iterator():l1.iterator();
Iterator<Integer> shorter = s2<=s1?l2.iterator():l1.iterator();
while(shift>0){
result.addLast(longer.next());
shift--;
}
while(longer.hasNext()){
result.addLast(longer.next()+shorter.next());
}
return result;
}
Sorry for the duplication...
The actual problem statement is as follows:
each given lists represents a number(each node contains the single digit). Now we need to return a linked list which contains the sum of those to numbers.
The below code is working. And it's time complexity and space complexity are O(max(m,n)).
public static ListNode reverse(ListNode head) {
ListNode previous = null;
ListNode current = head;
ListNode forward;
while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public static ListNode sumOfTheLists(ListNode head1, ListNode head2)
{
if(head1 == null && head2 == null)
{
return null;
}
if(head1 == null && head2 != null)
{
return head2;
}
if(head1 != null && head2 == null)
{
return head1;
}
LinkedList result = new LinkedList();
ListNode rhead1 = reverse(head1);
ListNode rhead2 = reverse(head2);
int temp = 0;
while(rhead1 != null || rhead2 != null)
{
if(rhead1 != null && rhead2 != null)
{
temp += (Integer)rhead1.element+(Integer)rhead2.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
rhead2 = rhead2.next;
}
else
{
if(rhead1 != null)
{
temp += (Integer)rhead1.element;
temp = addDigits(result, temp);
rhead1 = rhead1.next;
}
if(rhead2 != null)
{
temp += (Integer)rhead2.element;
temp = addDigits(result, temp);
rhead2 = rhead2.next;
}
}
}
if(temp != 0)
{
result.insertLast(temp);
}
return reverse(result.head);
}
private static int addDigits(LinkedList result, int temp) {
if( temp >= 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
return temp;
}
How many times are you going to post the same solution?
We get it, its correct.
Just as a next time advice, if you actually want people to look into your code, also explain in one line the approach you have taken in the code.
For example in this case you have reversed the original linked lists, added them node by node taking care of the carry and then returned the reverse of the resulting linked list.
isn't it required to give the solution without modifying the given lists ? you are reversing them here !
I guess you cannot provide a result without reversing the list for the given original example, where you need to start summation from the last Nodes and backward. So the steps would be
1. Reverse both lists
2. Start summing nodes from each list by going through the links
Solution without reversing the lists
h1 = 8->9->9->9
h2 = 9->9
Result = 9->0->9->8
Algo:
1. Loops through both to find which one is larger. Say larger is largehead (lh) and smaller list is (sh)
2. keep pushing larger node data to head of result (h3) . example in above case 9->8
3. Now both lh, sh will point to equal lists, add corresponding items, take care of carry over
to add to result head node. Then prepend the sum node to result.
4. Finally reverse the result node h3 to obtain the result.
typedef struct node
{
int data;
struct node *next;
node():data(0),next(NULL){}
} Node, *pNode;
void display(pNode p)
{
pNode curr = p;
while(curr)
{
cout << curr->data << ",";
curr = curr->next;
}
cout << endl;
}
void reverse(pNode &h1)
{
// Back->Mid->Front
pNode b = NULL;
pNode m = h1;
pNode f = NULL;
while(m)
{
f = m->next;
m->next = b;
b = m;
m = f;
}
h1 = b;
}
pNode sumList(pNode h1, pNode h2 )
{
cout << "display1" << endl;
display(h1);
cout << "display2" << endl;
display(h2);
int counth1 = count(h1);
int counth2 = count(h2);
pNode h3 = NULL;
pNode lh = NULL;
pNode sh = NULL;
if (counth1 >= counth2 )
{
lh = h1;
sh = h2;
}
else
{
lh = h2;
sh = h1;
}
int diff = counth1 - counth2;
if (diff < 0)
{
diff = diff * (-1);
}
pNode tmp = NULL;
while (diff > 0)
{
tmp = new Node();
tmp->data = lh->data;
tmp->next = h3;
h3 = tmp;
lh = lh->next;
diff--;
}
cout << "h3 no common" << endl;
display(h3);
// Now common lengths on both largehead and smallhead;
int carry;
while(lh && sh)
{
tmp = new Node();
tmp->data = (lh->data + sh->data) % 10;
carry = (lh->data + sh->data) / 10;
// keep taking the carry forward in h3.
// Note h3 head contains the last result where we need to add the carry.
Node *tmp2 = h3;
if (carry > 0 && tmp2 ==NULL)
{
// carry over in first number.
// Add a extra node for holding carry over.
//example: 9 + 9 = 18 => 81 is reverse order.
//Insert the 1 now, later we will prepend the sum (8 in example)
tmp2 = new Node();
tmp2->data = carry;
tmp2->next = h3;
h3 = tmp2;
}
else
{
while(carry > 0 && tmp2 !=NULL)
{
int olddata = tmp2->data;
tmp2->data = (olddata + carry) % 10;
carry = (olddata + carry) / 10;
tmp2 = tmp2->next;
}
}
tmp->next = h3;
h3 = tmp;
lh = lh->next;
sh = sh->next;
cout << "iteration " << endl;
display(h3);
}
cout << "before reverse" << endl;
display(h3);
reverse(h3);
cout << "after reverse" << endl;
display(h3);
return h3;
}
Start the addition from left to right (from most significant to least significant digit). You have three cases, depending of the sum of two digits:
= 9: keep the nine and increase a counter
< 9: write counter x nine, write sum, reset counter
> 9: increase last digit, write counter x zero, write sum (modulo 10), reset counter
I'll work on the following example:
2 568 794 +
1 438 204
--------- =
4 006 998
Add 2 + 1 = 3: case 3.
list = (3), counter = 0
Add 5 + 4 = 9: case 1
list = (3), counter = 1
Add 6 + 4 = 9: case 1
list = (3), counter = 2
Add 8 + 8 = 16: case 3
list = (4, 0, 0, 6), counter = 0
Add 7 + 2 = 9: case 1
list = (4, 0, 0, 6), counter = 1
Add 9 + 0 = 9: case 1
list = (4, 0, 0, 6), counter = 2
Add 4 + 4 = 8: case 2
list = (4, 0, 0, 6, 9, 9, 8), counter = 0
Is there any other Optimal solution?
Time complexity O(max(m,n)). Space Complexity: No extra space.
- akumarb2010 December 28, 2011