Microsoft

  www.microsoft.com
Work in HR? Unlock Free Profile

Microsoft Software Development Engineer In Test (SDET) Interview Question

I interviewed in Seattle, WA and was asked:
"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."
Add Tags [?]
Answer

Part of a Software Development Engineer In Test (SDET) Interview Review - one of 3,373 Microsoft Interview Reviews

Answers & Comments

0
of 0
votes

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

- Anonymous on Nov 18, 2013
0
of 0
votes

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
of 0
votes

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
of 0
votes

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

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.