9
\$\begingroup\$

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.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ If you're applying for a job in software development and you have no experience, it's probably a good idea to read up on some basic standards for professional software development. In this case, I'd look up a popular unit-test framework for C++. \$\endgroup\$ – mcv Mar 17 at 12:12
  • \$\begingroup\$ under any circumstances would solve Turing's Halting Problem. You'd earn a Nobel Prize for that. Maybe they wanted to hear "but you can try your best" \$\endgroup\$ – tofro Mar 18 at 10:45
  • \$\begingroup\$ @tofro This is irrelevant for the question but where I applied, you could have a Nobel and still be unemployed applying for work . \$\endgroup\$ – user10191234 Mar 18 at 13:36
11
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ I can't make a 1-char edit, but in the case where you test 113, you are still calling test() with 112, which seems like an mistake? \$\endgroup\$ – Korosia Mar 16 at 10:42
  • \$\begingroup\$ @Korosia it's a mistake that have now been fixed. Thank you for pointing it out. \$\endgroup\$ – Polygorial Mar 16 at 10:47
  • \$\begingroup\$ Great. Other than that, good answer! +1 \$\endgroup\$ – Korosia Mar 16 at 10:49
  • \$\begingroup\$ @Polygorial Thank you for your valuable input, I literally know nothing about testing (it was not taught in my college) so my idea was to test all elements of the vector that's why there is test (vec,7), it was a programming job and was caught off guard with the question and failed, I am still trying to find a way to implement what you've said. \$\endgroup\$ – user10191234 Mar 16 at 11:26
  • 1
    \$\begingroup\$ @user10191234 when you create automatic tests the goal is that all tests should pass, you test for the expected result only. Note that the expected result can be an exception as well, the important thing is that it's tested and the test succeeds when it gets that exception. I think you should look into a test framework since it's much easier to write tests using one. \$\endgroup\$ – Polygorial Mar 16 at 11:56
8
\$\begingroup\$

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);
}
\$\endgroup\$
2
  • \$\begingroup\$ Why not use the STL? Perhaps that line length has something to do with it, rendering the function almost unreadable... \$\endgroup\$ – AnnoyinC Mar 16 at 22:00
  • 1
    \$\begingroup\$ @AnnoyinC Maybe to a novice C programmer. A Modern C++ programmer with knowledge of how the language is designed to be used doesn't care. \$\endgroup\$ – Casey Mar 16 at 22:43
7
\$\begingroup\$

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()).
\$\endgroup\$
6
\$\begingroup\$

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).
\$\endgroup\$
4
\$\begingroup\$

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.

\$\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.