Amazon Interview Question for Software Engineer in Tests






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

1). I'm taking that the numbers are represented as below:
123: NULL <--- 1 <--- 2 <--- 3
789: NULL <--- 7 <--- 8 <--- 9

2). For the resultant list, I'm re-using the nodes of the first list.
3). The nodes of the second list are freed.

<snip>
cry = 0;
tmp = l2->next;
while (l1->next && l2->next) {
l1 = l1->next; // Header assumed.
l2 = tmp;
tmp = l2->next;
dig = (l1->val + l2->val + cry) % 10;
rem = (l1->val + l2->val + cry) / 10;
l1->val = dig;
cry = rem;
free(l2); // deallocating each node as it's traversed.
}

if (! l1->next) { //l2 has more digits
l1->next = l2->next;
l2->val += cry;
} else { //l1 has more digits than l2.
l2->next = l1;
l1->val += cry;
}
</snip>


Please correct, if there are any mistakes.

Thanks & Regards,
Hari.

- Hari October 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node *insertAtBegin(node *start, int n)
{
   node *temp = (node *)malloc(sizeof(node));
   temp->data = n;
   temp->next = start;
   return temp;
}

node *reverseList (node *start)
{
   node *prev = NULL;
   node *temp;
   while (start)
   {
      temp = start->next;
      start->next = prev;
      prev = start;
      start = temp;
   }
   return prev;
}

node *addNums(node *num1, node *num2)
{
   num1 = reverseList(num1);
   num2 = reverseList(num2);

   node *tmp1 = num1, *tmp2 = num2;
   node *num3 = NULL;

   int carry = 0, sum;

   while (num1 && num2)
   {
      sum = num1->data + num2->data + carry;
      num3 = insertAtBegin(num3,sum%10);
      carry = sum/10;
   }

   num1 = num1 ? num1 : num2;
   
   while (num1)
   {
      sum = num1->data + carry;
      num3 = insertAtBegin(num3,sum%10);
      carry = sum/10;
   }

   if (carry)
      num3 = insertAtBegin(num3,carry);

   num1 = reverseList(tmp1);
   num2 = reverseList(tmp2);

   return num3;

}

- CyberS1ren November 24, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple Algorithm:
Assuming L1 and L2 are given and sum is stored in L3

1. Reverse L1;
2. Reverse L2;
3. put=0;keep=0;
4. While (L1 or L2) 
       sum=L1.data + L2.data + keep;
       if(sum >10) then put=sum-10; keep=1
       else put=sum; keep=0
       L3.insert(put)
       L1.moveForward
       L2.moveForward
   End While;
   if(keep!=0) then L3.insert(keep)
   //take care of condition when either L1 or L2 becomes empty
5. L3.reverse
6. return L3

- Rakesh Kumar November 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about multiplication?

- Anonymous March 09, 2011 | 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