J'ai un entretien technique en C++/algorithmique

Le 26 avril 2021 à 16:02:52 improve2 a écrit :

Le 26 avril 2021 à 16:01:27 :

Le 26 avril 2021 à 15:56:07 El-Kheysitas10 a écrit :

Le 26 avril 2021 à 15:53:25 :

Le 26 avril 2021 à 15:48:37 :

Le 26 avril 2021 à 15:47:43 :

Le 26 avril 2021 à 15:43:38 :

Le 26 avril 2021 à 15:00:25 :
Apres faut voir comment tu codes et a quelle vitesse la theorie c'est cool mais bon

t'es au courant que dans l'industrie le pourcentage de temps passé à coder est proche de 4%? Coder vite ne sert à rien, coder intelligemment et savoir optimiser si.

Premature optimization is the root of all evil

c'est des conneries ça, à part si tu veux te traîner une dette technique que personne ne résoudra jamais

Non c'est pas des conneries.
Il faut coder proprement c'est le plus important, et optimiser si besoin.

Ca sert à rien de chercher à optimiser aux petits oignons si ce n'est pas nécessaire.
Je donne l'exemple d'une enum par exemple si on veut chercher une valeur pour un attribut donné.

Une façon triviale et d'itérer et de sélectionner le premier élément qui vérifie le prédicat d'égalité sur l'attribut. Une façon optimisée est de déclarer une HashMap en constante avec en clé l'attribut et en valeur l'enum (on passe ainsi de O(n) à du O(1)).

Sauf que celui qui fait cette petite optimisation sur une enum de 3 éléments qui est appelé une fois par appel n'a rien compris au code.

raconte pas ta vie igo

Je suis dev C++ dans l'industriel et je confirme qu'il vaut mieux coder proprement que "optimisé"

ça fonctionne > c'est propre >>> c'est rapide

Sur mon projet on a une optimisation (vitesse x3 je crois) du module central de calcul qui a toujours pas été mergée dans le tronc de dev depuis plus de 2 ans. C'est la dernière des priorités.

C'est surtout pratique pour les autres devs qui pourront potentiellement travailler sur le même code.

Oui. C'est quasiment impossible de travailler seul sur un logiciel.

Le 26 avril 2021 à 16:05:21 :

Le 26 avril 2021 à 16:02:52 improve2 a écrit :

Le 26 avril 2021 à 16:01:27 :

Le 26 avril 2021 à 15:56:07 El-Kheysitas10 a écrit :

Le 26 avril 2021 à 15:53:25 :

Le 26 avril 2021 à 15:48:37 :

Le 26 avril 2021 à 15:47:43 :

Le 26 avril 2021 à 15:43:38 :

Le 26 avril 2021 à 15:00:25 :
Apres faut voir comment tu codes et a quelle vitesse la theorie c'est cool mais bon

t'es au courant que dans l'industrie le pourcentage de temps passé à coder est proche de 4%? Coder vite ne sert à rien, coder intelligemment et savoir optimiser si.

Premature optimization is the root of all evil

c'est des conneries ça, à part si tu veux te traîner une dette technique que personne ne résoudra jamais

Non c'est pas des conneries.
Il faut coder proprement c'est le plus important, et optimiser si besoin.

Ca sert à rien de chercher à optimiser aux petits oignons si ce n'est pas nécessaire.
Je donne l'exemple d'une enum par exemple si on veut chercher une valeur pour un attribut donné.

Une façon triviale et d'itérer et de sélectionner le premier élément qui vérifie le prédicat d'égalité sur l'attribut. Une façon optimisée est de déclarer une HashMap en constante avec en clé l'attribut et en valeur l'enum (on passe ainsi de O(n) à du O(1)).

Sauf que celui qui fait cette petite optimisation sur une enum de 3 éléments qui est appelé une fois par appel n'a rien compris au code.

raconte pas ta vie igo

Je suis dev C++ dans l'industriel et je confirme qu'il vaut mieux coder proprement que "optimisé"

ça fonctionne > c'est propre >>> c'est rapide

Sur mon projet on a une optimisation (vitesse x3 je crois) du module central de calcul qui a toujours pas été mergée dans le tronc de dev depuis plus de 2 ans. C'est la dernière des priorités.

C'est surtout pratique pour les autres devs qui pourront potentiellement travailler sur le même code.

Oui. C'est quasiment impossible de travailler seul sur un logiciel.

Perso déjà que quand je vais sur mon propre code je refacto toujours, quand je vais sur celui des autres...

Le 26 avril 2021 à 14:53:37 :
Une question simple :Comment fonctionne une recherche binaire ?

Tu veux dire arbre binaire de recherche (BST) ? C'est un arbre qui vérifie la propriété que pour chaque noeud u (excepté feuilles) a une key dont la valeur est comprise entre les keys de ces enfants (< ou >) ; c'est une structure qui généralement à toutes ces opération en O(log n) s'il est parfaitement balancé. Je sais qu'il existe d'autres BST sympathiques comme le splay tree (pour le cache), B-tree, tango tree etc.

Le 26 avril 2021 à 14:55:41 :
comment tu obtiens une coupe minimale à partir d'un flot maximal ?

Tu trouves l'ensemble A des sommets qui sont atteignables depuis la source dans le graphe résiduel : toutes les arrêtes (u, v) tel que u \in A et v \in V\A définissent la coupe min.

Le 26 avril 2021 à 15:02:24 :
Donne un algo qui génère toutes les permutations d'une liste donnée en entrée?

std::next_permutation Le problème n'est pas nécessairement évident, surtout que qu'il existe des permutations spécifiques à certains problèmes qui respectent d'autres contraintes.

Le 26 avril 2021 à 15:04:41 :
meilleur algo pour inverser une matrice tridiagonale?, sa complexité?

Ca sent la décomposition de Cholemski/LU

Le 26 avril 2021 à 16:34:01 :

Le 26 avril 2021 à 14:53:37 :
Une question simple :Comment fonctionne une recherche binaire ?

Tu veux dire arbre binaire de recherche (BST) ? C'est un arbre qui vérifie la propriété que pour chaque noeud u (excepté feuilles) a une key dont la valeur est comprise entre les keys de ces enfants (< ou >) ; c'est une structure qui généralement à toutes ces opération en O(log n) s'il est parfaitement balancé. Je sais qu'il existe d'autres BST sympathiques comme le splay tree (pour le cache), B-tree, tango tree etc.

Il parlait plutôt de la recherche dichotomique (binary search en anglais ).

Le 26 avril 2021 à 15:21:46 :
Pourquoi le C++ dans ses dernieres versions est le langage le plus elegant ?
Elegant dans quel sens ?
Depuis C++11 ou C++20 ?

Elegant dans le sens où tu peux définir des fonctions très générales avec des templates ; peu de code mais une utilisation puissante. Le keyword auto, les algorithmes de la STL, les foncteurs, les différents paradigmes supportés etc. à la fin on se rapproche quasiment d'une écriture mathématique, c'est pour ça que j'apprécie de langage

Le 26 avril 2021 à 15:24:50 :
Code la fonction la plus optimisée possible pour trier un tableau de chaines de caractères par ordre alphabétique.

Counter sort en O(n)

Le 26 avril 2021 à 15:32:05 :
Meilleur topic depuis mon arrivée sur le forum, ma question, c'est quoi un arbre bicolore?

Red-Black tree ? C'est un BST qui s'équilibre automatiquement lors des insertions d'élements ; ça évite d'avoir un arbre de type chaîne et donc d'avoir des opérations en O(log n) même dans le pire cas. De mémoire je ne me souviens plus exactement du fonctionnement, mais j'imagine que tout se base sur l'invariance des rotations dans un arbre.

Le 26 avril 2021 à 15:36:03 :

Le 26 avril 2021 à 12:54:28 :

Le 26 avril 2021 à 12:24:27 :
Pourquoi tu utilises le c++ et pas le python

Parce que le C++ dans ses dernières versions est le langage de programmation le plus élégant

Le 26 avril 2021 à 12:24:36 :
Difference entre une volatile et une globale

Quand on déclare un membre volatile dans une classe, les méthodes peuvent être définies comme const même si ce membre est modifié ; j'imagine que ce keyword a d'autres possibilités. Une variable globale est une variable accessible à tous les scopes.

tu confonds volatile et mutable, tu viens de fail ton entretien, retour à pôle emploi

Ayaaa c'est pas des keywords que j'ai beaucoup utilisé, je crois même que volatile est déprécié ddepuis C++11 non ? merci khey

Le 26 avril 2021 à 16:37:23 :

Le 26 avril 2021 à 16:34:01 :

Le 26 avril 2021 à 14:53:37 :
Une question simple :Comment fonctionne une recherche binaire ?

Tu veux dire arbre binaire de recherche (BST) ? C'est un arbre qui vérifie la propriété que pour chaque noeud u (excepté feuilles) a une key dont la valeur est comprise entre les keys de ces enfants (< ou >) ; c'est une structure qui généralement à toutes ces opération en O(log n) s'il est parfaitement balancé. Je sais qu'il existe d'autres BST sympathiques comme le splay tree (pour le cache), B-tree, tango tree etc.

Il parlait plutôt de la recherche dichotomique (binary search en anglais ).

Ah oui effectivement, mais ça c'est l'algo des bébés, y'a pas grand chose à en dire, c'est le premier algo "Diviser pour régner" qu'on aborde en général

Le 26 avril 2021 à 16:43:46 :
Tu fais de la programmation fonctionnelle ? T'en penses quoi ?

Je préfère ça que la POO pour être honnête Le problème de la POO c'est que la hiérarchie entre classes est d'un casse-tête sans nom dans des gros projets, je préfère la souplesse de la programmation fonctionnelle/générique

Le 26 avril 2021 à 16:47:01 :
Qu'est ce qui permet d'assurer que l'algo du simplex termine ?

ça dépend des règles de séléction des variables que l'on entre/sort
tu insères celle qui a le coeff plus élevé dans la fonction objectif et tu sors la plus contraignante

Le 26 avril 2021 à 16:47:01 :
Qu'est ce qui permet d'assurer que l'algo du simplex termine ?

Ca se termine quand les coûts réduits sont négatifs pour un problème max Je crois qu'il existe certaines règles pour éviter des cas de dégénerance/cycling, comme la règle de Bland.

Le 26 avril 2021 à 16:46:37 :

Le 26 avril 2021 à 16:43:46 :
Tu fais de la programmation fonctionnelle ? T'en penses quoi ?

Je préfère ça que la POO pour être honnête Le problème de la POO c'est que la hiérarchie entre classes est d'un casse-tête sans nom dans des gros projets, je préfère la souplesse de la programmation fonctionnelle/générique

La hierarchie des classes c'est pas un pb de POO mais des dev qui en abusent.
On applique normalement le principe "composition over inheritance".

Sinon la prog fonctionnelle avec notamment du récursif ça peut devenir vite un gros casse-tête (sans parler des monad, effects etc.. ).

Le 26 avril 2021 à 16:50:46 :

Le 26 avril 2021 à 16:47:01 :
Qu'est ce qui permet d'assurer que l'algo du simplex termine ?

ça dépend des règles de séléction des variables que l'on entre/sort
tu insères celle qui a le coeff plus élevé dans la fonction objectif et tu sors la plus contraignante

Le 26 avril 2021 à 16:51:08 :

Le 26 avril 2021 à 16:47:01 :
Qu'est ce qui permet d'assurer que l'algo du simplex termine ?

Ca se termine quand les coûts réduits sont négatifs pour un problème max Je crois qu'il existe certaines règles pour éviter des cas de dégénerance/cycling, comme la règle de Bland.

Ok t'as l'air chaud l'op

Cool j'ai répondu à toutes les questions qui concernent le C++ alors que j'ai commencé ce langage serieusement y a un mois

Sinon des questions pour l'auteur :

Différence entre une classe abstraite et un interface ?
Peut-on avoir des constructeurs virtuels, pourquoi ?
Opérateurs qui permet de caster une instance d'une classe enfant à une classe mére et vice-versa de maniére sûre ?

Le 26 avril 2021 à 17:06:03 :
Comment tu fais pour t'entrainer l'OP ? J'aime beaucoup le C++ mais en maths appliquées c'est pas non plus comme si on devait recourir à plus qu'un #include <vector> , j'utilise des template , des functor, des auto un peu partout mais rien de plus....

Faut que tu fasses des projets persos, je te conseille aussi d'inspecter le code source des librairies que tu utilises sur Github et comprendre leur fonctionnement, surtout celles qui se basent sur les derniéres versions du C++