Feature Design Question

Question

I only had a question about how I design a simple function - find the second largest number in the Int array.

int findSecondLargest(int * arr, int len){ int second = 0; ... return second; } 

However, I was asked the following questions about how I solve problems.

• If len is less than 2 (I think we can return a special value like 0 or MinInt.)
• But if the second largest is 0. (Since in this case I cannot distinguish between the error and the normal return value, so I could throw an exception)
• If the array is {1,1,1} (since 1 is the largest number and not the second largest, so I can throw an exception)

I am really embarrassed. I think it’s impossible to cope with all situations. Usually we should document the use of our function instead of throwing an exception.

Hope some tips. Thanks

// The body of the function is written by me. I really like the design proposed by Donotalo and PigBen

Answer 1

Following the standard library model, when searching for a sequence, we do not return the value that we are looking for, we return the iterator to the value (pointer in this case). If we do not find the value, we return the iterator to one last element, the signature will look like this:

 // end is not the last element, it is one past the last element int * findSecondLargest(int * begin, int * end); 

Answer 2

Is the body function set by the interviewer? If not, I would write a function that returns the index of the second largest element in the array. If a second item is not found (for example, cases of errors), my function will return len to indicate that the second largest item was not found.

Answer 3

The problem with returning a "special value", such as 0, is that the second largest number in the array may be 0. How would you tell the difference?

A function, as written, cannot use this return value to indicate when an error occurred. You can either reorganize it to return an error code, and use the out parameter to fill in the found value (very C-style), or you can throw an exception (more C ++-style).

EDIT:

It just seemed to me that if the return value is the index of the second largest number in the array, you can use negative numbers as "special values".

Answer 4

The specification of the use of the function does not exclude the possibility of processing corner cases. It just means that you explicitly document the behavior of the function in such cases.

Whether you will throw an exception or return a certain (magic) value is up to you. You can also ask to change the type of return so that you have a richer diagnosis.

In any case, it’s good practice to think about the entire cost area. For example, here you also forgot to handle the case of arr being NULL or len negative.

Answer 5

Uses GCC-specific argument-argument-macro-variables-variables for testing, but in any case the main ideas:

If len is less than 2 (I think we can return a special value like 0 or MinInt.)

• Here I return a NULL pointer, not a pointer safe for markup, so there is no problem with having 0 or MinInt in the data.

But if the second largest is 0. (Since in this case I cannot distinguish between the error and the normal return value, so I could make an exception)

The exception to reasonable input is pretty seriously bad!

If the array is {1,1,1} (since 1 is the largest number and not the second largest, so I can throw an exception)

This can be argued, but this is the behavior that I modeled, also returning NULL.

So:

• distinguish a condition from an unreasonable condition using pointers against NULL
• the second highest value can be maintained by tracking the largest when we repeat once

The code is a bit choppy, but FWIW:

 #include <iostream> template <typename T, int N> T* second_largest(T (&arr)[N]) { if (N < 2) return NULL; T* largest = &arr[0]; T* second = NULL; for (int i = 1; i < N; ++i) { if (arr[i] > *largest) { second = largest; largest = &arr[i]; } else if (arr[i] != *largest && (!second || arr[i] > *second)) second = &arr[i]; std::cout << "i " << i << ", largest " << (largest ? *largest : -1) << ", second " << (second ? *second : -1) << '\n'; } return second; } #define TEST(ASSERTION, ARRAY...) \ { \ int x[] = { ARRAY }; \ int* p = second_largest(x); \ assert(ASSERTION); \ std::cout << #ASSERTION << " passed for " << #ARRAY << '\n'; \ } int main() { TEST(*p == 4, 1, 3, 2, 5, 4, 0); TEST(!p, 1, 1, 1); TEST(!p, 1); TEST(*p == 1, 1, 2); TEST(*p == 1, 2, 1); TEST(*p == 1, 1, 2, 0); std::cout << "all tests passed\n"; }