Fast way to compute the area covered by parallel lines that can overlap

Question

City is represented by matrix M x N, where rows are enumerated from 1 to N, and columns are enumerated from 1 to M.

Tramways always go straight along the row. Starting point of tramway is (r, c1) and ending point is (r, c2), where r is the number of row, c1 - starting column and c2 - ending column.

We need to determine the number of cells, not occupied by tramways. Attention: tramways can overlap within one row.

Input format: first line contains 3 integer values: N - number of rows, M -number of columns, K - number of tramways. Each next line i from total K lines contains 3 integer values: r, c1, c2.

Output format: integer value that represents the number of cells, not occupied by tramways.

Limitations:

1 <= N, M <= 10^9

0 <= K <= 1000

1 <= r <= N

1 <= c1, c2 <= M

Language: C or C++

Solution:

#include <fstream>

template <class T> struct Node
{
    T value;
    Node *left;     // less
    Node *right;    // more
    bool flag;

    Node(T value) : value(value), left(0), right(0), flag(false)
    {
    }

    virtual ~Node()
    {
    }
};

template <class T> class BST
{
protected:
    Node<T> *root;

    virtual Node<T>* constructHelper(T value)
    {
        return new Node<T>(value);
    }

    Node<T>* getHelper(Node<T> **p, T value)
    {
        Node<T> *node, *root, *arr[3];

        root = *p;

        if (root->value > value)
        {
            if (!root->left)
            {
                node = root->left = constructHelper(value);

                if (!root->right) root->flag = true;
            }
            else
            {
                node = getHelper(&root->left, value);

                if (root->flag)
                {
                    if (root->left->left)
                    {
                        arr[2] = root->left->left;
                        root->left->left = 0;

                            arr[1] = root->left;
                            root->left->flag = false;
                            root->left = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[1];
                        root->left = arr[2];
                        root->right = arr[0];

                        *p = root;
                    }
                    else if (root->left->right)
                    {
                        arr[2] = root->left->right;
                        root->left->right = 0;

                            arr[1] = root->left;
                            root->left->flag = false;
                            root->left = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[2];
                        root->left = arr[1];
                        root->right = arr[0];

                        *p = root;
                    }
                }
            }
        }
        else if (root->value < value)
        {
            if (!root->right)
            {
                node = root->right = constructHelper(value);

                if (!root->left) root->flag = true;
            }
            else
            {
                node = getHelper(&root->right, value);

                if (root->flag)
                {
                    if (root->right->right)
                    {
                        arr[2] = root->right->right;
                        root->right->right = 0;

                            arr[1] = root->right;
                            root->right->flag = false;
                            root->right = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[1];
                        root->left = arr[0];
                        root->right = arr[2];

                        *p = root;
                    }
                    else if (root->right->left)
                    {
                        arr[2] = root->right->left;
                        root->right->left = 0;

                            arr[1] = root->right;
                            root->right->flag = false;
                            root->right = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[2];
                        root->left = arr[0];
                        root->right = arr[1];

                        *p = root;
                    }
                }
            }
        }
        else node = root;

        return node;
    }

    void removeHelper(Node<T> *root)
    {
        if (root->left) removeHelper(root->left);

        if (root->right) removeHelper(root->right);

        delete root;
    }

public:

    Node<T>* getNode(T value)
    {
        Node<T> *node;

        if (!root)
        {
            root = constructHelper(value);
            node = root;
        }
        else
        {
            node = getHelper(&root, value);
        }

        return node;
    }

    BST() : root(0)
    {
    }

    ~BST()
    {
        if (root) removeHelper(root);
    }
};

//......................................................................................................................

template <class T, unsigned long long columns_width> class ColumnBST;

template <class T, unsigned long long raws_width, unsigned long long columns_width> struct RawNode : public Node<T>
{
    ColumnBST<T, columns_width> *raws[raws_width];

    RawNode(T value) : Node(value)
    {
        for (T i = 0; i < raws_width; ++i) raws[i] = 0;
    }

    virtual ~RawNode()
    {
        for (T i = 0; i < raws_width; ++i) if (raws[i]) delete raws[i];
    }
};

template <class T, unsigned long long raws_width, unsigned long long columns_width> class RawBST : public BST<T>
{
    virtual Node<T>* constructHelper(T value)
    {
        return new RawNode<T, raws_width, columns_width>(value);
    }

public:

    ColumnBST<T, columns_width>* getRaw(T r)
    {
        T x, y;
        RawNode<T, raws_width, columns_width> *node;

        --r;

        x = r / raws_width;
        y = r % raws_width;

        node = (RawNode<T, raws_width, columns_width>*)getNode(x);

        if (!node->raws[y]) node->raws[y] = new ColumnBST<T, columns_width>();

        return node->raws[y];
    }
};

//......................................................................................................................

template <class T, unsigned long long columns_width> class RailList;

template <class T, unsigned long long columns_width> struct ColumnNode : public Node<T>
{
    RailList<T, columns_width> *rails;

    ColumnNode(T value) : Node(value), rails(0)
    {
    }

    virtual ~ColumnNode()
    {
        if (rails) delete rails;
    }
};

template <class T, unsigned long long columns_width> class ColumnBST : public BST<T>
{
    virtual Node<T>* constructHelper(T value)
    {
        return new ColumnNode<T, columns_width>(value);
    }

public:

    T addRail(T c1, T c2)
    {
        T a, b, value;
        ColumnNode<T, columns_width> *node;

        --c1;
        --c2;

        a = c1 / columns_width;
        b = c2 / columns_width;

        if (a == b)
        {
            node = (ColumnNode<T, columns_width>*)getNode(a);
            if (!node->rails) node->rails = new RailList<T, columns_width>();

            value = node->rails->addRail(c1 % columns_width, c2 % columns_width);
        }
        else
        {
            node = (ColumnNode<T, columns_width>*)getNode(a);
            if (!node->rails) node->rails = new RailList<T, columns_width>();

            value = node->rails->addRail(c1 % columns_width, columns_width - 1);
            ++a;

            while (a < b)
            {
                node = (ColumnNode<T, columns_width>*)getNode(a);
                if (!node->rails) node->rails = new RailList<T, columns_width>();

                value += node->rails->addRail(0, columns_width - 1);
                ++a;
            }

            node = (ColumnNode<T, columns_width>*)getNode(a);
            if (!node->rails) node->rails = new RailList<T, columns_width>();

            value += node->rails->addRail(0, c2 % columns_width);
        }

        return value;
    }
};

//......................................................................................................................

template <class T> struct RailNode
{
    RailNode *next;
    T c1, c2;

    RailNode(T c1, T c2) : next(0), c1(c1), c2(c2)
    {
    }
};

template <class T, unsigned long long columns_width> class RailList
{
    RailNode<T> *rail;
    T total, min, max;

    T addRailHelper2(RailNode<T> *rail, T c1, T c2)
    {
        T value;

        if (!rail->next)
        {
            rail->next = new RailNode<T>(c1, c2);

            value = (c2 - c1) + 1;
        }
        else
        {
            value = addRailHelper(rail->next, c1, c2);
        }

        return value;
    }

    T addRailHelper(RailNode<T> *rail, T c1, T c2)
    {
        T value;

        if ((c1 > rail->c2) || (c2 < rail->c1))
        {
            value = addRailHelper2(rail, c1, c2);
        }
        else if ((c1 < rail->c1) || (c2 > rail->c2))
        {
            value = 0;

            if (c1 < rail->c1)
            {
                value += addRailHelper2(rail, c1, rail->c1 - 1);
            }

            if (c2 > rail->c2)
            {
                value += addRailHelper2(rail, rail->c2 + 1, c2);
            }
        }
        else value = 0;

        return value;
    }

    void removeRailHelper(RailNode<T> *rail)
    {
        RailNode<T> *node;

        while (rail)
        {
            node = rail->next;
            delete rail;
            rail = node;
        }
    }

public:

    RailList() : rail(0), total(0), min(0), max(0)
    {
    }

    ~RailList()
    {
        if (rail) removeRailHelper(rail);
    }

    T addRail(T c1, T c2)
    {
        T value;
        RailNode<T> *next, *node;

        if (!rail)
        {
            rail = new RailNode<T>(c1, c2);

            value = (c2 - c1) + 1;

            min = c1;
            max = c2;

            total = value;
        }
        else
        {
            if (total != columns_width)
            {
                if ((c1 > max) || (c2 < min))
                {
                    node = new RailNode<T>(c1, c2);

                    next = rail->next;
                    rail->next = node;
                    node->next = next;

                    value = (c2 - c1) + 1;
                }
                else
                {
                    value = addRailHelper(rail, c1, c2);
                }

                if (c1 < min) min = c1;
                if (c2 > max) max = c2;

                total += value;
            }
            else value = 0;
        }

        return value;
    }
};

//......................................................................................................................

template <class T, unsigned long long raws_width, unsigned long long columns_width> class City
{
    T n, m, k, i, count;
    RawBST<T, raws_width, columns_width> *raws;

public:

    City(T n, T m, T k) : i(0), count(0), raws(0)
    {
        if (((n >= 1) && (n <= 1000000000)) && ((m >= 1) && (m <= 1000000000)) && (k <= 1000))
        {
            this->n = n;
            this->m = m;
            this->k = k;
        }
        else throw std::out_of_range("");
    }

    ~City()
    {
        if (raws) delete raws;
    }

    T getResult()
    {
        return ((n * m) - count);
    }

    void addRail(T r, T c1, T c2)
    {
        ColumnBST<T, columns_width> *raw;

        if (((i < k) && (r >= 1) && (r <= n)) && ((c1 >= 1) && (c1 <= m)) && ((c2 >= 1) && (c2 <= m) && (c2 >= c1)))
        {
            if (!raws) raws = new RawBST<T, raws_width, columns_width>();

            raw = raws->getRaw(r);

            count += raw->addRail(c1, c2);

            ++i;
        }
        else throw std::out_of_range("");
    }
};

//......................................................................................................................

int main(int argc, char* argv[])
{
    std::fstream input_file("input.txt", std::ios_base::in);

    unsigned long long n, m, k;

    input_file >> n;
    input_file >> m;
    input_file >> k;

    City<unsigned long long, 32, 10000000> *city = new City<unsigned long long, 32, 10000000>(n, m, k);

    unsigned long long r, c1, c2;

    for (unsigned long long i = 0; i < k; ++i)
    {
        input_file >> r;
        input_file >> c1;
        input_file >> c2;

        city->addRail(r, c1, c2);
    }

    unsigned long long result = city->getResult();

    delete city;

    std::fstream output_file("output.txt", std::ios_base::out);

    output_file << result;

    return 0;
}

And it was rejected by employer (Intern C++ developer position). Can you help to figure out whether it is terrible or not? I was never interested in algorithms and I fell like I am C coder that throws all abstractions away. Thank you.

Answer 1

This looks like a very complicated and memory-hungry solution. With all that complexity, I'd expect to see quite a few unit tests in the review, but there are none.

I'd expect to see a solution that reads in all the inputs, grouping them by row number (e.g. in a std::multimap), and then iterates over the rows, combining overlapping rails to obtain the total for that row.

There are a number of errors reported when I compile with a recent standard:

• Node as a base-class name needs to be Node<T> (in the initializers of RawNode and RawBST)
• declarations in dependent base BST<long long unsigned int> are not found by unqualified lookup, so we need to write this->getNode(a) instead of just getNode(a) in a bunch of places.

Even with the errors fixed, there's almost a hundred lines of warnings, when I compile with g++ -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++. I recommend acting on them.