Cracking The Coding Interview/Q 2.5

From Software Engineers Wiki
Jump to: navigation, search

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 Ts 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: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
  • Output: 2 -> 1 -> 9.That is, 912.

FOLLOW UP

Suppose the digits are stored in forward order. Repeat the above problem.

EXAMPLE

  • Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
  • Output: 9 -> 1 -> 2.That is, 912.

Answer

It keeps the number in a linked list in little-endian format (LSB is in the first node of the list). This is easier in handling arithmetic and to take care of carry bit.

#include <iostream>
#include <initializer_list>
#include <list>

class CNumList {
private:
        /* Keep the number in little-endian order */
        std::list<int> m_digits;
public:
        CNumList() {}
        CNumList(std::initializer_list<int> il) : m_digits(il) {}
        CNumList(CNumList &x) : m_digits(x.m_digits) {}
        CNumList(int x) {
                /* assume x is positive number */
                do {
                        m_digits.push_back(x % 10);
                        x /= 10;
                } while (x != 0);
        }
public:
        int get(void) {
                int sum = 0;
                int mul = 1;
                for (auto &x : m_digits) {
                        sum += x * mul;
                        mul *= 10;
                }
                return sum;
        }
        void print_little(void) {
                /* print forward: LSB to MSB */
                for (auto &x : m_digits)
                        std::cout << x;
        }
        void print_big(void) {
                std::list<int>::iterator il = m_digits.end();

                /* if begin() == end(), the list is empty */
                if (il == m_digits.begin())
                        return;

                /* print backward: MSB to LSB */
                do {
                        --il;
                        std::cout << *il;
                } while (il != m_digits.begin());
        }
        CNumList& operator += (CNumList &opnd) {
                std::list<int>::iterator il1 = m_digits.begin();
                std::list<int>::iterator il2 = opnd.m_digits.begin();
                int carry = 0;

                while (il2 != opnd.m_digits.end() || carry) {
                        int sum = carry;

                        sum += (il1 == m_digits.end()) ? 0 : *il1;
                        sum += (il2 == opnd.m_digits.end()) ? 0 : *il2;

                        if (sum >= 10) {
                                carry = 1;
                                sum -= 10;
                        } else
                                carry = 0;

                        if (il1 == m_digits.end()) {
                                m_digits.push_back(sum);
                                il1 = m_digits.end();
                        } else {
                                *il1 = sum;
                                ++il1;
                        }

                        if (il2 != opnd.m_digits.end())
                                ++il2;
                }

                return *this;
        }
};

Sample test using initializer list on constuctor.

                CNumList num1 { 7, 1, 6 };
                CNumList num2 { 5, 9, 2 };

                num1.print_big();
                std::cout << " + ";
                num2.print_big();
                std::cout << " = ";
                num1 += num2;
                num1.print_big();
                std::cout << std::endl;

Sample test with pre-defined samples.

        try {
                for (i = 0; i < sizeof(samples) / sizeof(samples[0]); ++i) {
                        CNumList num1(samples[i][0]);
                        CNumList num2(samples[i][1]);
                        int sum;

                        num1.print_big();
                        if (num1.get() != samples[i][0])
                                throw samples[i][0];

                        std::cout << " + ";
                        num2.print_big();
                        if (num2.get() != samples[i][1])
                                throw samples[i][1];

                        std::cout << " = ";
                        sum = samples[i][0] + samples[i][1];
                        num1 += num2;
                        if (num1.get() != sum)
                                throw sum;
                        num1.print_big();

                        std::cout << " (" << sum << ")\n";
                }
        } catch (int e) {
                std::cout << "Error with " << e << std::endl;
        }

Test with random numbers.

        try {
                for (i = 0; i < 100; ++i) {
                        int rand1 = random() & 0x3fffffff;
                        int rand2 = random() & 0x3fffffff;
                        CNumList num1(rand1);
                        CNumList num2(rand2);
                        int sum;

                        num1.print_big();
                        if (num1.get() != rand1)
                                throw rand1;

                        std::cout << " + ";
                        num2.print_big();
                        if (num2.get() != rand2)
                                throw rand2;

                        std::cout << " = ";
                        sum = rand1 + rand2;
                        num1 += num2;
                        if (num1.get() != sum)
                                throw sum;
                        num1.print_big();

                        std::cout << " (" << sum << ")\n";
                }
        } catch (int e) {
                std::cout << "Error with " << e << std::endl;
        }
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox