2
\$\begingroup\$

Just for fun I did the following exercise from "Cracking the coding interview. 4th edition":

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE Input: (3 -> 1 -> 5), (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

Although my solution it seems to return valid results it is significantly different from the proposed solution. I implemented my own structures and I haven't used recursion.

I know both solutions are valid, but in case of a real interview: How would the interviewer consider my answer? Which caveats should I consider?

public class ex24
{
    public static void Run()
    {

        var n1 = CreateNumber(5, 1, 3);
        var n2 = CreateNumber(2, 9, 5);

        Figure xF = n1;
        Figure xY = n2;
        int alpha = 0;

        Figure prev = null;
        Figure ini;
        do
        {
            int n1v = n1 != null ? n1.Value : 0;
            int n2v = n2 != null ? n2.Value : 0;

            int sum = n1v + n2v + alpha;

            decimal f = sum / (decimal)10;
            alpha = (int)f;
            sum = (int)((f - alpha) * 10);

            if (prev == null)
            {
                ini = new Figure(sum);
                prev = ini;
            }
            else
            {
                prev.Next = new Figure(sum);
                prev = prev.Next;
            }

            n1 = n1 != null ? n1.Next : null;
            n2 = n2 != null ? n2.Next : null;

        } while (n1 != null || n2 != null || alpha != 0);

      // Result is stored on 'ini'.

    }
    public class Figure
    {
        public Figure Next;
        public int Value;

        public Figure(int value)
        {
            this.Value = value;
        }

        public override string ToString() =>"" + this.Value;

    }

    public static Figure CreateNumber(params int[] values)
    {
        Figure ini = new Figure(values[values.Length - 1]);
        Figure prev = ini;
        for (var ix = values.Length - 2; ix >= 0; ix--)
        {
            prev.Next = new Figure(values[ix]);
            prev = prev.Next;
        }

        return ini;
    }

}
\$\endgroup\$
  • \$\begingroup\$ Why not use the linked list type from the framework (System.Collections.Generic.LinkedList<T>)? \$\endgroup\$ – user190892 Feb 10 at 14:32
3
\$\begingroup\$
  • Strictly speaking, the code does not solve the problem. As an interviewer I'd expect a clearly defined

        List add(List l1, List l2)
    

    method.

    At the very least, rename Run to add, and do not CreateNumbers in it, but pass them as parameters.

  • Since it is guaranteed that every node contains a digit, the sum may never exceed 19. This means, among other things, that there is no need for decimal. Everything can be done with primitive types, e.g.

        alpha = sum > 10;
        sum -= alpha * 10;
    

    As a side note, the entity you call alpha is traditionally called carry.

  • The do {} while() approach seems to create more problems than it solves. An immediate manifestation is duplication of n1 != null tests. Consider

        while (n1 != null && n2 != null) {
            // addition logic here
            n1 = n1.Next;
            n2 = n2.Next;
        }
    

    and promote the carry along the remainder of the longer list in a separate loop.

  • Consider creating a dummy head for a resulting list. It is a standard trick to avoid a special case of prev == null, e.g.

        Figure dummy = new Figure;
        Figure tail = dummy;
    
        while (....) {
            ....
            tail.next = new Figure(sum);
            tail = tail.next;
        }
        ....
        return dummy.next;
    
\$\endgroup\$
  • \$\begingroup\$ alpha = sum > 10; sum -= alpha * 10 won't work in C# (something like carry = sum / 10; sum -= carry * 10 would). Also worth noting that List is the .NET type which represents a dynamic array, rather than a linked-list (LinkedList) \$\endgroup\$ – VisualMelon Feb 10 at 10:10
  • \$\begingroup\$ On 3rd point. Both numbers might not have the same length so checking for a null value is required, moreover, the while condition has to be an OR instead of AND. \$\endgroup\$ – arturn Feb 10 at 18:30
  • \$\begingroup\$ @arturn The third point explicitly said promote the carry along the remainder of the longer list in a separate loop. True, I didn't spell out this separate loop, pretty much intentionally. \$\endgroup\$ – vnp Feb 10 at 18:48
  • \$\begingroup\$ @vnp Sure ;) Sorry,I misunderstood the sentence! \$\endgroup\$ – arturn Feb 13 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.