Unit test for a maximum-finding function

Question

A while ago, I got this question as a part of an interview test which asked to write a function to find the biggest number in a vector and write all the unit tests required to show that the code works under any circumstance using any language or pseudo-code.

To the best of my knowledge, one would need a testing framework in order to do that, so I wrote this and I got a rejection email a couple of hours later.

#include <cassert> 
#include <vector>

int largest (std::vector<int> vec ) {

int max = vec[0];
for (int i=1; i<vec.size(); i++)
   if (vec[i] > max)
      max = vec[i];
return max;
}

void test (std::vector<int> vec, int i) {
assert (largest (vec) == i);
}

int main() {
std::vector<int> vec = { 7, 50, 16, 8, 25, 9, 12,112 };
test (vec, 112);
test (vec, 7);

return 0;
}

I have zero experience in professional software development and I used C++ since I find it easy to compile and run.

What did I do wrong? What should I have written? Any input would be great.

Answer 1

I'm not a C++ developer, and can't comment on the details of the code. But I can comment on the test cases and the general style of the code.

A good test should be enough to recreate the code from reading just the test cases. Especially when you get the task to make sure the code works under any circumstance.

Successful test cases

Let's have a look at your first test case:

std::vector<int> vec = { 7, 50, 16, 8, 25, 9, 12,112 };
test (vec, 112);

You have a vector with a max number 112, and you test for that. If I were to implement the most simple way of accepting your test I would do this (using pseudocode):

return 112;

Let's change add another test to avoid that implementation:

std::vector<int> vec = { 7, 50, 16, 8, 25, 9, 12,113 };
test (vec, 113);

Now I can't just return 112, I have to actually do something else. I would use either of these as my implementation:

return vec.lastElement();
return vec[7];

More test cases needed to fix those problems. I could go on, but I think you understand. I think the following test cases could be a good base:

{ 111 }
{ 7, 50, 16, 8, 25, 9, 12, 112 }
{ 7, 50, 16, 8, 113, 25, 9, 12 }
{ 114, 7, 50, 16, 8, 25, 9, 12 }
{ -1, -2, -3 }
{ -1, 0, 1 }
{ -333, 0 }
{ 0, 123456 }

That's a good start, now we have a lot of test cases with numbers. But we're still missing one important test:

std::vector<int> vec = { };

I have no idea what you want to be returned in this case, but it is a valid case that needs to be handled.

Naming tests

Now we have 10 tests for that simple function. But we need to look at the code to see what the test is testing, and it might not be obvious in all cases. It would be better to have a name for each test that explains what the test is testing in plain English. This is easier with testing frameworks, but a comment would also make the intention clear.

Indent

Looking at your code I struggle to see where the functions begin and end. Make sure to indent properly.

Is this a failing test?

Your second test is:

std::vector<int> vec = { 7, 50, 16, 8, 25, 9, 12,112 };
test (vec, 7);

What is this testing? My understanding is that 7 shouldn't be returned, failing this test. I don't understand why this is added, please explain in a comment.

Answer 2

A function that returns the largest value in a vector would certainly have to check if the vector is actually non-empty. You aren't handling that case and are just assuming "the first" element is the biggest...if there is no "first" element, your program will crash in Debug builds or invoke UB in Release builds.

Also, were there restrictions not mentioned here? Why not use the STL?:

if(const auto iter = std::max_element(std::cbegin(vec), std::cend(vec)); iter != std::cend(vec)) {
    //iter now contains a const_iterator containing the largest element...
} else {
    //The vector was empty.
    //iter now contains std::cend(vec);
}

Answer 3

Unit tests are great, and perfectly suited to self-contained functions such as this. However, assert() is not a testing tool. It's more use as a kind of "magic comment" to tell our readers what we believe to be true (and sometimes to help optimise our code).

One of the great problems of assert() is that its diagnostics are weak. On failure, it prints the test that evaluated false, but doesn't show any of the values that contributed to the failure.

I would recommend using one of the many test frameworks (as you hint at in the question) which provide functions or macros such as EXPECT_EQ(), EXPECT_NE(), etc. They are constructed for writing tests, and usually output the actual and expected values to help with diagnosis.

Another problem with assert() is that when it fails, it's a sign that your program is broken and should be terminated before it causes further damage. What we want is something that records the error, and perhaps terminates that single test, but continues with the other tests in the suite to give us more of that valuable diagnostic information. Again, using a standard test framework would solve that for you.

If you insist on writing your own comparison function, it isn't hard to add the features I've mentioned. As a prospective colleague, I'd prefer to work with someone who can make good use of existing tools rather than reinvent the wheel - that makes their work easier to read and modify as well as less time-consuming to initially write.

The choice of tests is puzzling. The very first test I would write would be one that accepts an empty vector. Think also of other boundary cases - a single-element vector would probably be next.

Consider the test here:

std::vector<int> vec = { 7, 50, 16, 8, 25, 9, 12,112 };
test (vec, 112);

We could make this test pass with this (wrong) function:

int largest(const std::vector<int>& vec) {
    return vec.back();
}

But our test would not detect the error.

---

Some aspects of the function itself are cause for concern:

• Assumption that "number" in the question necessarily means int.
• Passing std::vector by value, rather than by const ref.
• Failure to deal appropriately with empty vectors.
• Nested flow-control (if/for) without braces.
• Failure to take advantage of Standard Library functions (estd::max_element()).

Answer 4

A few things to consider / be careful of:

• Pass by reference (and probably an immutable one at that) - so you are not copying the vector AND you are showing that you are only using methods that don't have an effect of changing the vector. e.g

int largest (std::vector<int> const & vec ) {

• Boundary cases (empty vector should give what value for largest?)

• Consider one of the xUnit frameworks (such as cppunit; it doesn't matter which one, just use one) - then you can write simple asserts in a way that debugs easier (expected value first, tested value second, when the test fails the error is value doesn't match expect).

CPPUNIT_ASSERT_EQUAL( 112, largest(vec) );

• Need lots of different test inputs: reverse order, negative numbers, same number, repeated tests (to confirm same inputs same outputs).

Answer 5

In a practical scenario, a good unit test should cover all edge cases. Hence, you should test the empty list, and you should test the cases where the largest element is at the beginning, at the end, and somewhere in the middle of the vector. There might be even more reasonable test-cases. There is, however, the possibility that you have been confronted with a trick question.

Strictly speaking, the task to "write all the unit tests required to show that the code works under any circumstance" is impossible. Consider the following code:

const size_t N = 10;

int largest(std::vector<int> a)
{
    if (a.size() > N)
        return a.at(0);

    int candidate = a.at(0);
    for (size_t i=1; i < a.size(); ++i) {
        if (a[i] > candidate) {
            candidate = a[i];
        }
    }
    return candidate;
}

This function works perfectly for all vectors that are no longer than 10 elements, however, fails for almost all vectors that have more than 10 elements. You might say: "okay, so I have to include vectors that have to have at least 11 elements." In this case, however, I could set N to 100 or 1000. The point here being, with just a finite number of unit tests and without inspecting the code, it is impossible to prove that the code is correct. I can always give you a function that works for all unit tests and fails for all other inputs. In short:

a test can only show the presence of an error, never the absence of errors.

Depending on the type of person you have been dealing with, this might have been the "correct" answer. Without asking, you will probably never know.