Questions d’entretien d’ingénieur logiciel

Méthode — Recherche du complément

L’approche exhaustive teste chaque paire, ce qui prend O(n^2). Une meilleure approche utilise une table de hachage associant chaque valeur à son indice. En parcourant le tableau, pour chaque nombre x, la valeur recherchée est target - x. Si ce complément figure déjà dans la table, nous renvoyons l’indice courant et l’indice enregistré. Sinon, nous enregistrons x avec son indice et poursuivons. L’idée essentielle pour l’exactitude est qu’au moment de traiter l’indice i, la table contient exactement les valeurs des indices précédents. Ainsi, si une paire valide se termine en i, nous la trouvons immédiatement. Cela évite également de réutiliser le même élément, car la correspondance ne porte que sur les éléments précédents. La complexité temporelle est O(n), puisque chaque valeur est insérée et recherchée une fois. La complexité spatiale est O(n) pour la table. Les cas limites comprennent les doublons, les nombres négatifs, zéro et l’absence de paire valide si la consigne autorise ce cas.

Méthode — Fenêtre glissante avec indice de dernière occurrence

Utilisez une fenêtre glissante qui ne contient que des caractères uniques. Conservez un pointeur gauche et une table associant chaque caractère à son indice le plus récent. Parcourez la chaîne avec le pointeur droit. Si le caractère courant a déjà été vu dans la fenêtre actuelle, déplacez le pointeur gauche juste après son indice précédent. Mettez ensuite à jour l’indice du caractère et mémorisez la longueur maximale de la fenêtre. Le détail important est que le pointeur gauche ne doit avancer que vers la droite. Si un caractère a été vu avant la fenêtre actuelle, il ne doit pas réduire la fenêtre. La mise à jour est donc left = max(left, lastSeen[char] + 1). La complexité temporelle est O(n), puisque chaque caractère est traité une fois et que le pointeur gauche n’avance que dans un sens. La complexité spatiale est O(k), où k est la taille du jeu de caractères. Les cas limites comprennent la chaîne vide, des caractères tous uniques, des caractères tous identiques et Unicode lorsque le langage ne traite pas les caractères comme les octets.

Méthode — Clé canonique

Les anagrammes possèdent la même composition de caractères. Créez une clé canonique pour chaque mot et regroupez les mots par cette clé dans une table de hachage. La clé la plus directe est la suite triée des caractères du mot. Par exemple, « eat », « tea » et « ate » correspondent tous à « aet ». Si les chaînes sont courtes, trier chaque mot est simple et fiable. Si l’alphabet est limité aux lettres anglaises minuscules et que les chaînes sont longues, un tuple de 26 fréquences peut être plus rapide, car il évite un tri O(k log k) pour chaque mot. Avec le tri, la complexité temporelle est O(n * k log k), où n représente le nombre de chaînes et k leur longueur moyenne. Avec un comptage sur un alphabet fixe, elle peut être O(n * k). La complexité spatiale est O(n * k) pour le résultat et les clés. Les cas limites comprennent les chaînes vides, les doublons, les règles de casse et les caractères non anglais.

Méthode — Trois pointeurs : précédent, courant, suivant

Utilisez trois pointeurs. previous vaut d’abord null et current pointe vers la tête. Pour chaque nœud, enregistrez next = current.next, redirigez current.next vers previous, puis déplacez previous vers current et current vers next. Lorsque current devient null, previous est la nouvelle tête. L’invariant est que previous pointe vers la partie déjà inversée et current vers le premier nœud qui ne l’est pas encore. Il est indispensable d’enregistrer next avant de modifier current.next ; sinon, le reste de la liste est perdu. La complexité temporelle est O(n) et la complexité spatiale O(1). Les cas limites comprennent une liste vide, un seul nœud et la nécessité de transformer la tête d’origine en queue avec next défini sur null.

Méthode — Contraintes d’intervalle

Une erreur fréquente consiste à vérifier seulement que chaque nœud est supérieur à son enfant gauche et inférieur à son enfant droit. Cela ne suffit pas, car tout le sous-arbre doit respecter les contraintes héritées des ancêtres. Utilisez un DFS avec une borne inférieure et une borne supérieure. Pour chaque nœud, vérifiez lower < node.value < upper. L’enfant gauche reçoit la même borne inférieure et la valeur courante comme borne supérieure. L’enfant droit reçoit la valeur courante comme borne inférieure et la même borne supérieure. Si un nœud sort de son intervalle, renvoyez false. La complexité temporelle est O(n), car chaque nœud est visité une fois. La complexité spatiale est O(h) pour la profondeur de récursion, h étant la hauteur de l’arbre. Les cas limites comprennent les doublons, les bornes minimales et maximales des entiers, l’arbre vide et les arbres dégénérés. Précisez si les doublons sont autorisés et, le cas échéant, de quel côté.

Méthode — Parcours en largeur par niveau de distance

Modélisez chaque cellule libre comme un nœud du graphe et chaque déplacement vers le haut, le bas, la gauche ou la droite comme une arête de même poids. Puisque chaque déplacement a le même coût, un BFS fournit le plus court chemin. Partez de la cellule source, ajoutez-la à une file avec une distance de 0 et marquez-la comme visitée. Pour chaque cellule retirée de la file, explorez les voisines valides, non visitées, situées dans les limites et qui ne sont pas des obstacles. La première fois que la cible est atteinte, la distance est minimale. L’exactitude découle du fait que le BFS traite les nœuds par distance croissante. Lorsqu’une cellule a été visitée, une visite ultérieure ne peut pas produire un chemin plus court dans un graphe non pondéré. La complexité temporelle est O(rows * cols), car chaque cellule est visitée au plus une fois. La complexité spatiale est O(rows * cols) pour la file et l’ensemble des cellules visitées. Les cas limites comprennent une source ou une cible bloquée, une source identique à la cible, l’absence de chemin et l’autorisation éventuelle des déplacements en diagonale.

Méthode — Table des nœuds d’origine vers leurs clones

Utilisez une table de hachage qui associe chaque nœud d’origine à son clone. Pendant le DFS ou le BFS, créez le clone du nœud visité s’il n’existe pas. Clonez ensuite chaque voisin, récursivement ou itérativement, puis ajoutez le voisin cloné à la liste d’adjacence du nœud cloné. La table des nœuds visités résout deux problèmes : elle évite les boucles infinies dans les graphes cycliques et préserve les références partagées afin que le graphe cloné possède la même topologie que l’original. La complexité temporelle est O(V + E), où V représente les nœuds et E les arêtes. La complexité spatiale est O(V) pour la table et la pile ou la file de parcours, sans compter le graphe produit. Les cas limites comprennent une entrée null, les boucles sur soi-même, les graphes non connexes si la consigne demande seulement de cloner depuis un nœud de départ et les voisins dupliqués.

Méthode — Programmation dynamique ascendante sur le montant

Définissez dp[a] comme le nombre minimal de pièces nécessaire pour former le montant a. Initialisez dp[0] = 0 et toutes les autres valeurs à l’infini. Pour chaque montant de 1 à la cible, essayez chaque pièce. Si a - coin est positif ou nul, alors dp[a] = min(dp[a], dp[a - coin] + 1). À la fin, si dp[target] vaut l’infini, renvoyez -1. La récurrence fonctionne parce que la dernière pièce d’une solution optimale doit faire partie des valeurs disponibles. Si cette dernière pièce vaut c, le montant restant est target - c, qui doit lui aussi être résolu de façon optimale. La complexité temporelle est O(amount * number of coins) et la complexité spatiale O(amount). Les cas limites comprennent un montant nul, les montants impossibles, une pièce de valeur 1, les valeurs dupliquées et les montants cibles très élevés.

Méthode — DP par position finale, puis optimisation par recherche binaire

Une solution claire de programmation dynamique définit dp[i] comme la longueur de la plus longue sous-séquence croissante se terminant à l’indice i. Pour chaque i, examinez tous les indices j précédents. Si nums[j] < nums[i], alors nums[i] peut prolonger la sous-séquence se terminant en j, donc dp[i] = max(dp[i], dp[j] + 1). La réponse est max(dp). Cette solution prend O(n^2) en temps et O(n) en mémoire. L’approche optimisée en O(n log n) conserve un tableau tails, où tails[length - 1] est la plus petite valeur finale possible d’une sous-séquence croissante de cette longueur. Pour chaque nombre, recherchez par dichotomie le premier élément de tails qui lui est supérieur ou égal, puis remplacez-le. La longueur de tails est celle de la plus longue sous-séquence croissante. En entretien, il est raisonnable de présenter d’abord la solution O(n^2) si le temps est limité, puis d’expliquer la version optimisée. Les cas limites comprennent les doublons, les tableaux décroissants, l’entrée vide et la question de savoir si la sous-séquence doit être strictement croissante.

Méthode — Ne construire que des préfixes valides

Utilisez le backtracking avec deux compteurs : open pour les parenthèses ouvrantes utilisées et close pour les parenthèses fermantes. À chaque étape, vous pouvez ajouter une parenthèse ouvrante si open < n. Vous pouvez ajouter une parenthèse fermante si close < open. Cette deuxième condition garantit que chaque préfixe reste valide et évite de générer des chaînes incorrectes qu’il faudrait filtrer ensuite. Lorsque la longueur de la chaîne courante atteint 2n, ajoutez-la au résultat. L’algorithme n’explore ainsi que les préfixes valides et élague rapidement les états impossibles. Le nombre de sorties valides est le n-ième nombre de Catalan ; la taille de la sortie domine donc le temps d’exécution. La complexité spatiale comprend une profondeur de récursion O(n), en plus du résultat. Les cas limites comprennent n = 0 et n = 1, selon la définition de la consigne.

Méthode — Exigences → API → Génération d’identifiants → Stockage → Redirection → Passage à l’échelle

Exigences : les utilisateurs soumettent une URL longue et reçoivent une URL courte. Lorsqu’une personne consulte l’URL courte, elle doit être redirigée rapidement. Les fonctionnalités facultatives comprennent les alias personnalisés, l’expiration, l’analyse, la détection du spam et les comptes utilisateurs. API principales : createShortUrl(longUrl, optionalAlias, expiration) et redirect(shortCode). Modèle de données : shortCode, longUrl, userId, createdAt, expiresAt, status et, si nécessaire, métadonnées analytiques. Pour générer les identifiants, on peut utiliser des identifiants auto-incrémentés encodés en base62, des codes base62 aléatoires avec détection des collisions ou une génération distribuée. L’auto-incrémentation est simple, mais révèle le volume si elle n’est pas masquée. Les identifiants aléatoires se distribuent facilement, mais exigent une gestion des collisions. À une échelle modérée, des codes base62 aléatoires assortis d’une contrainte d’unicité en base de données conviennent. Le chemin de lecture est prioritaire. La redirection doit être rapide : charger shortCode depuis le cache, se rabattre sur la base de données, vérifier l’expiration et l’état, puis renvoyer HTTP 301 ou 302. Utilisez 302 si l’analyse ou la modification de la destination est importante ; utilisez 301 pour les redirections permanentes bénéficiant d’une mise en cache plus forte par le navigateur. Passage à l’échelle : mettre les codes courts très consultés dans Redis ou dans un cache en périphérie, partitionner par shortCode si nécessaire, enregistrer les données analytiques de façon asynchrone dans une file, limiter le débit de création et exécuter des contrôles contre le spam et les logiciels malveillants. Surveillez la latence de redirection, le taux de succès du cache, le taux d’erreur, les signalements d’abus et la saturation de la base de données.

Méthode — Utilisateurs → Publications → Fanout → Classement → Lectures → Cohérence

Clarifiez le type de fil : abonnements sociaux, recommandations ou combinaison des deux. Supposons un fil d’abonnements dans lequel les utilisateurs créent des publications que leurs abonnés voient par pertinence ou par récence. Objets principaux : utilisateurs, relations d’abonnement, publications, médias, éléments du fil, mentions J’aime et commentaires, ainsi que signaux de classement. Les API comprennent createPost, getFeed, followUser, unfollowUser et interactWithPost. Il existe deux modèles courants de génération. Le fanout à l’écriture envoie chaque nouvelle publication dans les fils des abonnés au moment de sa création. Les lectures sont rapides, mais les écritures coûteuses pour les comptes très suivis. Le fanout à la lecture calcule le fil à la demande en récupérant les publications des comptes suivis. Les écritures sont peu coûteuses, mais les lectures plus lentes. Une approche hybride est fréquente : fanout à l’écriture pour les utilisateurs ordinaires et fanout à la lecture, ou traitement spécial, pour les célébrités. Architecture : le service de publications écrit les contenus, le service de graphe stocke les relations d’abonnement, le service de fil maintient les chronologies, le service de classement note les publications candidates, le cache conserve les fils très consultés et les médias sont stockés dans un stockage objet avec CDN. Des files gèrent le fanout asynchrone et les mises à jour du classement. Arbitrages : fraîcheur du fil ou qualité du classement, cohérence des changements d’abonnement, gestion des célébrités, invalidation du cache, spam, blocages liés à la confidentialité et rattrapage après une panne de file. Surveillez la latence de chargement, la fraîcheur, le retard du fanout, l’engagement, le taux de succès du cache, les erreurs de classement et les signalements d’abus.

Méthode — Connexions → Flux des messages → Persistance → Livraison → Fiabilité

Exigences : messages individuels et de groupe, livraison en ligne et hors ligne, historique, accusés de lecture, indicateurs de saisie et notifications push. Précisez si le chiffrement de bout en bout, les pièces jointes et la synchronisation multiappareil sont nécessaires. Les clients maintiennent des connexions WebSocket avec un service de passerelle. Lorsqu’un utilisateur envoie un message, la passerelle l’authentifie, attribue ou reçoit une clé d’idempotence, écrit le message dans un stockage durable, publie un événement et le livre aux destinataires connectés. Les utilisateurs hors ligne reçoivent des notifications push et peuvent récupérer l’historique plus tard. Modèle de données : conversation, participant, message, état de livraison, état de lecture et appareil ou session. Le stockage doit permettre des lectures efficaces par conversation et par date. Une base relationnelle convient à une échelle modérée ; des stockages distribués sont utilisés à plus grande échelle. Les pièces jointes doivent aller dans un stockage objet, pas dans la base des messages. Problèmes de fiabilité : envois dupliqués, livraison dans le désordre, reconnexions, messages manqués, fanout des grands groupes et exactitude de la présence. Utilisez des clés d’idempotence, des numéros de séquence croissants par conversation, des accusés de réception, une logique de nouvelle tentative et des API de synchronisation depuis le dernier élément vu. Surveillez la latence d’envoi, le taux de livraison réussie, le nombre de connexions WebSocket, le taux de reconnexion, le retard des files, les échecs de notifications push et les erreurs d’écriture dans le stockage.

Méthode — Valider → Délimiter → Changements récents → Décomposer les dépendances → Atténuer

Je commencerais par valider le signal. Je vérifierais si la hausse apparaît dans plusieurs outils de supervision et si elle touche le p50, le p95, le p99 ou seulement un endpoint précis. Je confirmerais également son effet sur les utilisateurs. Je délimiterais ensuite le problème par endpoint, région, zone de disponibilité, segment de clientèle, version, hôte, dépendance et type de requête. Une hausse générale suggère une dépendance partagée ou un déploiement ; une hausse circonscrite renvoie à une route, une requête, un client ou une zone d’infrastructure. J’examinerais ensuite les changements récents : déploiements, configuration, migrations de base de données, pics de trafic, feature flags, modifications du cache ou incidents de services aval. Les traces permettraient de décomposer la latence entre les services. Je vérifierais le temps des requêtes en base, le taux de succès du cache, le retard des files, le CPU, la mémoire, le ramasse-miettes, les pools de threads, les pools de connexions et les API externes. Si les utilisateurs sont touchés, l’atténuation précède la compréhension parfaite de la cause racine. Il faut revenir en arrière, désactiver un feature flag, augmenter la capacité, contourner une dépendance lente ou augmenter la durée de vie du cache si cela ne présente pas de risque. Après le rétablissement, il faut documenter la cause racine, la lacune de détection et le plan de prévention.

Méthode — Cas unitaires → Limites → Entrées invalides → Invariants

Je commencerais par clarifier les règles : types de remise, cumul, expiration, montant minimal, admissibilité de l’utilisateur, arrondi monétaire et inclusion éventuelle des taxes ou de la livraison. Les tests unitaires doivent couvrir les cas normaux, les limites, les entrées invalides et les interactions entre règles. Exemples : aucune remise, remise en pourcentage, montant fixe, remise supérieure au sous-total, seuil minimal exactement atteint, montant juste inférieur au seuil, remise expirée, utilisateur non admissible, plusieurs remises si elles sont autorisées et arrondi aux centimes. Je testerais aussi les invariants : le prix final ne doit jamais être négatif, la remise ne doit pas dépasser le sous-total admissible, les promotions expirées ne doivent pas s’appliquer et les calculs répétés doivent rester déterministes. Si cette logique touche aux paiements, j’ajouterais des tests d’intégration avec le service de tarification et des tests instantanés sur les factures produites. Pour sécuriser la production, je journaliserais les décisions de remise avec des codes de motif afin que le support et les ingénieurs puissent diagnostiquer les réclamations tarifaires sans conjectures.

Méthode — Exactitude → Maintenabilité → Risque → Clarté

J’examine le code par couches. Premièrement, résout-il le problème prévu tout en préservant l’exactitude ? Deuxièmement, est-il maintenable : noms clairs, limites raisonnables, absence de complexité inutile et style cohérent ? Troisièmement, quels sont les risques : migrations, concurrence, sécurité, performance, rétrocompatibilité et observabilité ? Quatrièmement, les tests couvrent-ils suffisamment le comportement modifié ? Une bonne revue de code ne sert pas à afficher sa supériorité. Elle doit améliorer le code tout en préservant la vitesse de l’équipe. Je distingue les problèmes bloquants des suggestions. Un bug d’exactitude, un problème de sécurité ou un risque de migration est bloquant. Une préférence de nommage ou une petite refactorisation peut ne pas l’être. Je recherche également les éléments de contexte manquants : comportement produit imprécis, cas limites non testés, chemins d’échec silencieux, gestion des erreurs insuffisante et absence de métriques autour des changements risqués.

Méthode — Contexte → Options → Arbitrages → Décision → Résultat

Choisissez une décision comportant de véritables arbitrages : développer ou acheter, SQL ou NoSQL, monolithe ou service, correctif rapide ou refactorisation profonde, cohérence forte ou disponibilité. Commencez par le contexte et les contraintes, puis expliquez les options envisagées. Une bonne réponse nomme clairement l’arbitrage. Par exemple : « L’option A nous permettait de livrer en une semaine, mais augmentait la charge opérationnelle. L’option B demandait trois semaines, mais supprimait un goulot d’étranglement. » Expliquez ensuite les preuves qui ont guidé la décision : trafic, échéance client, historique d’incidents, capacité de l’équipe ou feuille de route à long terme. Terminez par le résultat et ce que vous avez appris. Si la décision était imparfaite, précisez ce que vous feriez différemment. Les recruteurs apprécient davantage un jugement mature que la prétention que chaque décision était évidente.

Méthode — Incident → Impact → Réponse → Cause racine → Prévention

Si possible, utilisez un incident réel. Commencez par l’impact utilisateur : ce qui ne fonctionnait plus, les personnes touchées et la gravité. Expliquez ensuite votre rôle dans la réponse : détection, triage, retour en arrière, atténuation, communication ou analyse de la cause racine. Les meilleures réponses montrent une priorisation calme. Pendant un incident, rétablir le service importe davantage que prouver une théorie. Expliquez comment vous avez utilisé les journaux, les métriques, les traces, les feature flags, les retours en arrière ou la vérification des dépendances. Après l’atténuation, exposez la cause racine et la prévention. Les mesures utiles peuvent inclure de meilleurs tests, un déploiement plus sûr, de la supervision, un réglage des alertes, des procédures opérationnelles, des coupe-circuits, de la contre-pression ou des protections de migration. Ne blâmez personne. Les bonnes équipes améliorent les systèmes afin de rendre la même erreur plus difficile à reproduire.

Méthode — Objectif commun → Contraintes → Options → Arbitrages → Décision

Je commence par aligner l’équipe sur l’objectif utilisateur et l’objectif commercial. De nombreux désaccords n’opposent pas réellement l’ingénierie au produit ; ils reposent sur des hypothèses différentes. J’expliquerais clairement la contrainte technique : complexité, risque pour la fiabilité, calendrier, maintenabilité, sécurité ou performance. Je proposerais ensuite des options au lieu de répondre simplement non. Par exemple : livrer un MVP plus réduit, utiliser provisoirement un flux manuel, placer la fonctionnalité derrière un flag, séquencer le travail technique ou choisir un design plus simple qui résout néanmoins le problème utilisateur essentiel. Si l’arbitrage est important, je documente les options, les risques et la recommandation afin de rendre la décision transparente. L’objectif n’est pas que l’ingénierie gagne, mais que l’équipe prenne une décision claire en toute connaissance de cause.