11
\$\begingroup\$

This is not a novel interview problem. But I want to address it with the following points:

  1. Implement the algorithm with Object-Oriented Design principles in mind.

  2. Optimize the solution, if there are many continuous inputs.

  3. Write simple unit tests (without using unit testing framework like gtest, boost.test)

Basically, I followed the idea of Sieve of Eratosthenes algorithm. To optimize the solution if there are many continuous inputs, I maintain a vector which stores all the primes we have computed so far. If the new n is smaller than the previous maximal n, we can directly get the primes from "cache" without re-computing the primes again.

I'm specifically looking for suggestions on the algorithm itself, OOD or better unit tests.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class PrimeFinder {
    friend class PrimeFinderTest;
public:
    PrimeFinder(int n = 2) {
        is_prime_.push_back(false);
        is_prime_.push_back(false);
        is_prime_.push_back(true);
        primes_.push_back(2);
        n_ = n;
    }

    vector<int> get_primes(int n) {
        if(n <= n_) {
            return get_primes_subset(n);
        } else {
            extend_primes(n);
            return primes_;
        }
    }

private:
    vector<bool> is_prime_;
    vector<int> primes_;
    int n_;

    vector<int> get_primes_subset(int n) {
        auto iter = primes_.begin();
        while(iter != primes_.end()) {
            if(*iter <= n) ++iter;
            else break;
        }
        return vector<int>(primes_.begin(), iter);
    }

    void extend_primes(int n) {
        is_prime_.reserve(n + 1);
        is_prime_.insert(is_prime_.end(), n - n_, true);

        int bound = sqrt(n);
        for(int i = 2; i <= bound; ++i) {
            if(is_prime_[i]) {
                int j = i + i;
                while(j <= n) {
                    if(j > n_) {
                        is_prime_[j] = false;
                    }
                    j += i;
                }
            }
        }

        for(int i = n_ + 1; i <= n; ++i) {
            if(is_prime_[i]) primes_.push_back(i);
        }

        n_ = n;
    }
};

template <typename T>
string vec2str(const vector<T>& vec) {
    string str = "";
    for(auto n : vec) {
        str += to_string(n) + " ";
    }
    return str;
}

class PrimeFinderTest {
public:
    void test_get_primes_subset(vector<int> origin, int n) {
        PrimeFinder test;
        test.primes_ = origin;
        vector<int> subset = test.get_primes_subset(n);
        cout << vec2str(subset) << endl;
    }

    void test_extend_primes(vector<int> origin, vector<bool> origin_bool, int n) {
        PrimeFinder test;
        test.primes_ = origin;
        test.is_prime_ = origin_bool;
        test.n_ = test.is_prime_.size() - 1;
        test.extend_primes(n);
        assert(test.n_ == n);
        assert(test.is_prime_.size() == n + 1);
        cout << vec2str(test.primes_) << endl;
    }

    void test_get_primes(int n) {
        PrimeFinder test;
        cout << vec2str(test.get_primes(n)) << endl;
    }

    void test_get_primes_suite(vector<int> nums) {
        PrimeFinder test;
        for(int num : nums) {
            cout << vec2str(test.get_primes(num)) << endl;
        }
        cout << endl;
    }
};


int main() {
    PrimeFinderTest test;
    test.test_get_primes_subset(vector<int>({2,3,5,7,11,13,17,19}),7);
    test.test_get_primes_subset(vector<int>({2,3,5,7,11,13,17,19}),8);
    test.test_get_primes_subset(vector<int>({2,3,5,7,11,13,17,19}),15);

    test.test_extend_primes(vector<int>({2,3,5,7}),
                            vector<bool>({false, false, true, true, false, true, false, true, false}),
                            19);

    test.test_get_primes(2);
    test.test_get_primes(9);
    test.test_get_primes(16);
    test.test_get_primes(30);

    test.test_get_primes_suite(vector<int>({2, 9, 16, 30}));
    test.test_get_primes_suite(vector<int>({16, 9, 2, 30}));
    test.test_get_primes_suite(vector<int>({1,2,3,4,5}));

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ OO is for simulations and modelling, mathy and algorithmic code is much nicer pure imperative (or functional). Also finding the primes upto n is just (1..n).select(&:is_prime) or a sieve if performance is a concern. \$\endgroup\$ – Caridorc Aug 22 '15 at 17:18
  • \$\begingroup\$ @Quill Thanks for the editing! (and sorry for my poor English expression...). I have added some context and feel free to rephrase them if needed. Thanks! \$\endgroup\$ – yvetterowe Aug 22 '15 at 22:31
6
\$\begingroup\$

Namespaces

using namespace std; is considered bad practice. Short code is not a requirement in C++, clear code is preferred.

Return

return 0; is a legacy from C. In C++, it's no longer required to write this manually at the end of main. The compiler will take care of returning 'normal' if no errors where thrown or other returns (like -1) are encountered.

Naming

The following is confusing:

PrimeFinder test;
PrimeFinderTest test;

You have both multiple PrimeFinder around which you named test as a PrimeFinderTest named test. In all cases the variable name is not descriptive and together it's confusing.

Loops

Do you have a particular reason why the following is a while loop?

            while(j <= n) {
                if(j > n_) {
                    is_prime_[j] = false;
                }
                j += i;
            }

A for loop would be more readable here.

Now we're talking about that loop anyway, only use one letter variables like i and j when iterating (if at all, those extra bytes for full names won't bite you). Here, you're using both n and n_ without documenting what they are. That's a maintainability trap.

There's no rule against trailing underscores (my personal preference is not to use them), but in this case the difference between n and n_ is not distinctive enough. n_ = n; is also a good indication your naming could be improved.

\$\endgroup\$

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.