Question sur la conception des fonctions

Question

Je viens d'avoir une question d'entretien sur la façon de concevoir une fonction simple - trouver le deuxième plus grand nombre dans un tableau Int.

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

    return second;
}

Cependant, on m'a posé les questions suivantes sur la façon dont je gère ces problèmes.

1. Si len est inférieur à 2 (je pense que nous pouvons retourner une valeur spéciale, comme 0, ou MinInt.)
2. Mais, si le deuxième plus grand est 0. (Puisque dans ce cas, je ne peux pas différencier entre une erreur et une valeur de retour normale. donc je pourrais lancer une exception)
3. Si le tableau est {1,1,1} (puisque 1 est le plus grand nombre, et non le deuxième plus grand, je pourrais lancer une exception).

Je me sentais vraiment confus. Je pense qu'il n'est pas possible de faire face à toutes les situations. Nous devons généralement documenter l'utilisation de notre fonction, au lieu de lever une exception.

J'espère un conseil. Merci

//Le corps de la fonction est écrit par moi-même. J'aime beaucoup le design supposé par Donotalo et PigBen.

Answer 1

Suivant le modèle standard des bibliothèques, lors de la recherche d'une séquence, nous ne renvoyons pas la valeur que nous recherchons, mais un itérateur vers la valeur (un pointeur dans ce cas). Si nous ne trouvons pas la valeur, nous retournons un itérateur vers l'un des derniers éléments, la signature ressemblerait à ceci :

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

Answer 2

Le corps de fonction est-il donné par l'interviewer ? Sinon, j'écrirais une fonction qui renvoie l'indice du deuxième plus grand élément du tableau. Si aucun deuxième plus grand élément n'est trouvé (comme vos cas d'erreur), ma fonction renverrait len pour indiquer que le deuxième plus grand élément n'est pas trouvé.

Answer 3

Le problème que pose le renvoi d'une "valeur spéciale", telle que 0, est que le deuxième plus grand nombre du tableau podría est de 0. Comment pourriez-vous faire la différence ?

La fonction, telle qu'elle est écrite, ne peut pas utiliser sa valeur de retour pour indiquer qu'une erreur s'est produite. Vous pouvez soit la remanier pour qu'elle renvoie un code d'erreur et utiliser un paramètre out pour remplir la valeur trouvée (très C), soit lever une exception (plus C++).

EDITAR:

Il m'est venu à l'esprit que si la valeur renvoyée est le indice du deuxième plus grand nombre du tableau, vous pouvez utiliser des nombres négatifs comme "valeurs spéciales".

Answer 4

Le fait de spécifier l'utilisation de la fonction n'empêche pas de traiter les cas particuliers. Cela signifie simplement que vous documentez explicitement le comportement de la fonction dans de tels cas.

Vous pouvez décider de lever une exception ou de renvoyer une valeur (magique) spécifique. Vous pouvez également demander à modifier le type de retour afin de disposer d'un diagnostic plus riche.

Dans tous les cas, il est bon de réfléchir à l'ensemble du champ des contributions. Par exemple, ici vous avez aussi oublié de traiter le cas de arr être NULL o len être négatif.

Answer 5

Utilise la notation variable-number-of-args-to-macro spécifique à GCC juste pour tester, mais de toute façon, les idées de base sont :

Si la len est inférieure à 2 (je pense que nous pouvons retourner une valeur spéciale, comme 0, ou MinInt.)

• Ici, je renvoie un pointeur NULL plutôt qu'un pointeur de référence sûr, donc il n'y a pas de problème avec la présence de 0 ou MinInt dans les données.

Mais, si le deuxième plus grand est 0. (Puisque dans ce cas, je ne peux pas différencier entre une erreur et une valeur de retour normale. donc je pourrais lancer une exception)

Une exception pour une entrée raisonnable, c'est sérieusement mauvais !

Si le tableau est {1,1,1} (puisque 1 est le plus grand nombre, et non le deuxième plus grand, je pourrais lancer une exception).

C'est discutable, mais c'est le comportement que j'ai modélisé, également en retournant NULL.

Donc :

• différencier une condition trouvée d'une condition non trouvée en utilisant des pointeurs contre NULL
• la deuxième plus grande valeur peut être maintenue en suivant la plus grande au fur et à mesure de l'itération.

Le code est un peu brouillon, mais à titre indicatif :

#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";
}