Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

Is there any other Optimal solution?
Time complexity O(max(m,n)). Space Complexity: No extra space.

public static LinkedList sumOfTwoLists(LinkedList list1, LinkedList list2)
	{
		if(list1 == null)
		{
			return list2;
		}
		if(list2 == null)
		{
			return list1;
		}
		
		LinkedList result = null;
		int diffSize = list2.listSize();
		if(diffSize < list1.listSize())
		{
			diffSize = list1.listSize() - diffSize;
			ListNode temp1 = list1.head;
			result = new LinkedList(temp1.element);
			while(temp1.next != null && --diffSize > 0)
			{
				result.insertLast(temp1.next.element);
				temp1 = temp1.next;
			}
			
			ListNode temp2 = list2.head;
			while(temp1.next != null && temp2 != null )
			{
				result.insertLast((Integer)temp1.next.element+(Integer)temp2.element);
				temp1 = temp1.next;
				temp2 = temp2.next;
			}
		}
		else if(diffSize > list1.listSize())
		{
			diffSize = diffSize - list1.listSize();
			ListNode temp1 = list2.head;
			result = new LinkedList(temp1.element);
			while(temp1.next != null && --diffSize > 0)
			{
				result.insertLast(temp1.next.element);
			}
			
			ListNode temp2 = list1.head;
			while(temp1.next != null && temp2 != null )
			{
				result.insertLast((Integer)temp1.next.element+(Integer)temp2.element);
				temp1 = temp1.next;
				temp2 = temp2.next;
			}
		}
		else {
			ListNode temp1 = list2.head;
			ListNode temp2 = list1.head;
			result = new LinkedList(new Integer((Integer)temp1.element+(Integer)temp2.element));
			while(temp1.next != null && temp2.next != null )
			{
				result.insertLast((Integer)temp1.next.element+(Integer)temp2.next.element);
				temp1 = temp1.next;
				temp2 = temp2.next;
			}
		}
		return result;
	}

public int listSize() {
		int size = 0;
		ListNode temp = this.head;
		while (temp != null) {
			size++;
			temp = temp.next;
		}
		return size;
	}

- akumarb2010 December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

a previous thread is talking about the same question...I like this place

- Anonymous December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will work for it.
List1: 1 9 5
List2: 1 5
Result sum list: 1 10 10

- akumarb2010 December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL!

- Kshitij December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

tell me what will be the ans of 195+15 i think it will be 210

- Sanjay Kumar December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

try o do it without reversing the linklist

- Sanjay Kumar December 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- akumarb2010 December 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually it is without reversing linked lists!!!

- akumarb2010 December 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It will work. Following is out put
List1: 1 9 5
List2: 1 5
Result sum list: 1 10 10

- akumarb2010 December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but the expected output is

2->1->0

- Anonymous December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- akumarb2010 December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- akumarb2010 December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- akumarb2010 December 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey are we allowed to use some oher data structure like array inside the function

- sweet.prash December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First,we compute both lists' length,say m and n(say m>n)
Second,p1 ,p2points to head of lists,then move p1 to next until m-k==n
Final,add the data,p1++,p2++

- jasonborn009 December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- altstaterus December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sushant December 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Sushant. Next time I will take care of such things.

- Anonymous December 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

isn't it required to give the solution without modifying the given lists ? you are reversing them here !

- ashu December 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- UKSJayarathna January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I didn't read your code and Sushant's comment was helpful in understanding the approach. As far as , in-place algorithm requirement is concerned, we can reverse the linked lists again. Just reversing the linked list doesn't change the "stable" ness of algorithm as it can be restored.

- We Pin January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- msays2000 January 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AAYUSH KUMAR January 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dunno bout the space and time complexity issues.. but simplicity wise.. beat this.. :P

add the first LL to stack.. O(n)
add the second LL to stack O(m)
pop from both and add...
(n>m? O(n) : O(m))

- Mith January 27, 2012 | 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