Microsoft Interview Question: given two linked lists with a... | Glassdoor

Interview Question

Software Development Engineer In Test (SDET) Interview Seattle, WA

given two linked lists with a digit in each node, add the

  two linked lists together. the result must be a linked list with one digit in each node. use only one iteration of the two input lists.

Interview Answer

5 Answers


Is this to remove duplicates from linked list or just combining both the linked lists blindly?

Anonymous on Nov 18, 2013

assume the numbers you need to add are 560 and 890. the result should be 1450.

so linked list A will have 5 -> 6 -> 0
and linked list B will have 8 -> 9 -> 0
so you must add them together to produce 1 -> 4 -> 5 -> 0.

i believe the reason for an algorithm like this is to have a method of adding arbitrarily large numbers together. rather than storing an integer as int32 or int64, we can store the int as a linked list, which can be any size integer we want. Of course, the underlying 'int' we use for the data of the linked list only needs to be 4 bits to cover 0-9 in decimal.

ben on Nov 19, 2013

public static List AddTwoLists(List first, List second)
            return first.Zip(second, (a, b) => a + b).ToList();

Ben on Nov 21, 2013

i don't believe this answer is correct. you must account for cases where you will carry a 1. for example, if node A_i is 5 and node B_i is 7, then C_i = 2 and C_(i-1) = C_(i-1) + 1.

In short, you must consider the carry value. I don't see that your solution considers this. Your solution would make C_i = 12, but 12 is two digits, not one.

ben on Nov 21, 2013

I think the answer should traverse both link lists and add each node data and make a new link list with digit on each node of the answer. In this way we can traverse in N time and at the end if any nodes are left in second link list we can attach them at the end of new link list

A on Nov 3, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.