C++ help

[SwiftSpear]

I'm interviewing for a position at a local company, and part of the interview process is a coding assignment. The difficulty I'm having is that my C++ is self taught and I'm not as confident with the quality of my code as I would be if it were Java or Python. They know C++ isn't my best language at this point in time but I still want to do a good job with this assignment.

My code so far compiles and runs fine, I have some plans for improving the efficiency of the algorithm I'm using, and I'm going to add pseudo javadoc style comments for the methods, but I'm just wondering if anyone with more C++ experience, or professional C++ experience can critique my adherence to best practices or style issues.

My code:

Code: Select all

priority_queue < long long int > getFactors(long long int k) {
    /*
    a fairly naive algorithm that returns a priority queue containing
    all the integer divisors that fit into some integer
    */
    priority_queue<long long int> q;
    q.push(1); //all nums are divisible by 1
    q.push(k); //all nums are divisible by themselves
    long long int max = (k/2)+1;//there are no numbers that divide by more than 1 half themselves
    for(int i = 2; i<max; i++) {
        if(k%i == 0){
            q.push(i);
            q.push(k/i);
            max = k/i;
        }
    }
    return q;
}

int unfriendlyNumbers(vector < long long int > a,long long int k) {
    //validity checks
    if (0 > k || k > 10000000000000) {return -1;}
    if (a.size() > 1000000) {return -1;}
    
    //functional code
    priority_queue<long long int> factors = getFactors(k);
    int count = 0;
    bool good = false;
    while (!factors.empty()) {
        long long int test = factors.top();
        factors.pop();
        good = true;
        for (vector<long long int>::iterator it = a.begin(); it != a.end(); ++it) {
            if (*it % test == 0) {
                good = false;
                break;
            }
        }
        if (good) {
            count++;
        }
    }
    int ans = count;
    return ans;
}

[malric]

Not an expert either, and just had a quick look (so, not thinking much about the algorithm), but have 2 comments:
- why do you need the final "ans" variable? (can return directly count, and in this case it will not be more readable either)
- why do you need variable "good"? (you could do the "count++;" instead of "good = false;")

PS: a priority queue might a bit "expensive" for your case, as you can determine the factors more or less in order (probably you will need 2 vectors, but still might be "faster" than a priority queue).

[gajop]

Before showing a solution and have us discuss that, you should've described the problem exactly.

[Kloot]

Even without knowing what the problem is supposed to be (though I can guess), this has some "inexperienced" fingerprints over it:

• your code won't find repeated factors (125 = 5*5*5), be sure the assignment allows this
• use size_t instead of long long int, the "0 > k" already expresses you don't care about signed numbers
• "for(int i = 2; i<max; i++)" can loop forever when max > INT_MAX
• getFactors pushes the factors AND their quotients to the queue which is redundant
• use a std::list instead of a pqueue to store the factors, all you do is iterate over them in descending order
• pass this list to getFactors by reference from unfriendlyNumbers instead of copying it on return
• reconstruct the quotients in unfriendlyNumbers from the variable "test" and extend the "if (*it % test == 0)" part
• "vector < long long int > a" can be const&
• "vector<...>::iterator it" can be "vector<...>::const_iterator" can be "auto"
• unless part of the assignment the "validity checks" look bogus: eg. why would k=10000000000001 not be factorable?
• what gajop said

[jK]

[*] use size_t instead of long long int, nobody cares about signed numbers unless told otherwise

size_t can be 32bit unsigned, but his code (his k number range check) explicit needs minimum 64bit precision.

[Kloot]

ah, true (brings me to another point: don't use magic numbers, especially uncommented ones with many zeros)

[jK]

I would use 1e13, but in case of spring this would fail cause it defines a floating point number and in case of spring those are limited to 32bit floats, and so it wouldn't fit. Even when the compiler optimizes it to a int constant later, it's too risky that it clamps it somewhere between.
Too bad there is no 1e13U in c++.

[SwiftSpear]

Thanks for the advice Kloot! I really appreciate it.

Yeah, the validity checks were for things directly specified by the assignment, and I intentionally used the priority queue to order the items and avoid repeated factors (which you were correct in guessing were irrelevant to the assignment). I picked up from your criticism that my commenting needed some real work. Apologies for not being clear with what I was expecting the code to do. The assignment itself was this:

https://www.hackerrank.com/challenges/u ... ly-numbers

I already had it doing the thing I wanted to do, I was more worried about how awful my style was. I ended up spending way more time than I wanted chasing down an optimization red herring, which was really frustrating, but I learned something for next time (cheat earlier).

[AF]

Where is your unit test suite? Your functions have no Docblocks or equivalent

[SwiftSpear]

Where is your unit test suite? Your functions have no Docblocks or equivalent

The test cases are provided by the challenge set. The goal of the assignment is to pass as many test cases as possible.

I added doc blocks a little while after I posted this here.