Microsoft

www.microsoft.com
Engaged Employer

## 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.

0

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

Anonymous on Nov 18, 2013
0

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
0

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

Ben on Nov 21, 2013
0

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