Maîtrisez la fusion de k listes triées avec heap ou divide and conquer, O(N log k) et pièges Python. Lisez pour réussir l’entretien.
Les candidats qui se figent sur ce problème connaissent généralement déjà la forme du code. La question d’entretien sur la fusion de k listes triées n’a rien de mystérieux — c’est un test de reconnaissance de schéma, que la plupart des gens échouent non pas parce qu’ils ne savent pas écrire le heap, mais parce qu’ils ne savent pas expliquer pourquoi ils l’utilisent. L’intervieweur demande « pourquoi un heap ? », et la réponse qui sort est « parce que c’est efficace », ce qui est techniquement vrai mais pratiquement inutile. Ce que l’intervieweur attendait, c’était une explication de 20 secondes sur le fait qu’il s’agit d’un problème de fusion k-aire, sur ce que cela change dans la forme de la solution, et sur la raison pour laquelle l’approche choisie aboutit à un O(N log k) sans approximation.
C’est cet écart que cet article comble. Pas seulement le code — la décision, la justification et l’explication orale que vous pouvez donner sans vous disperser.
Voyez la fusion k way avant de toucher au code
Pourquoi ce n’est pas juste « fusionner deux listes » avec des étapes en plus
L’instinct consiste à voir ici une fusion de deux listes répétée plusieurs fois. Fusionnez la liste 1 et la liste 2, prenez le résultat, fusionnez-le avec la liste 3, et ainsi de suite. Cela fonctionne. Mais cela produit aussi une complexité en O(Nk) dans le pire cas, et cela signale à l’intervieweur que vous répondez à la mauvaise question.
La différence structurelle est la suivante : fusionner deux listes est une décision bilatérale à chaque étape — nœud de gauche ou nœud de droite. Fusionner k listes triées est une décision multilatérale — parmi les k frontières courantes, laquelle contient le plus petit nœud ? C’est un travail fondamentalement différent, qui appelle une structure de données différente. Quand vous reconnaissez qu’il s’agit d’une fusion k-aire, l’espace de solutions se réduit à deux options nettes : un min-heap qui suit explicitement la frontière, ou une stratégie divide and conquer qui orchestre des fusions par paires en couches équilibrées. Les deux sont correctes. Aucune n’est une « fusion de deux listes avec des étapes en plus ».
Les candidats qui paraissent fluides en entretien sont ceux qui nomment cette distinction avant de toucher au code. Ce n’est pas un piège — c’est le schéma. Une fois que vous voyez la fusion k-aire, le reste n’est qu’un détail d’implémentation.
Ce que l’énoncé teste réellement
L’intervieweur teste trois choses en même temps : la reconnaissance de schéma, la maîtrise de la complexité et votre capacité à expliquer pourquoi le prochain plus petit nœud ne peut venir que de l’une des k têtes de listes courantes — jamais d’un endroit plus profond dans une liste, puisque chaque liste est déjà triée.
Ce dernier point est l’invariant sur lequel repose toute la solution. À chaque étape, le plus petit nœud restant au niveau global doit être la tête de l’une des k listes restantes. Vous n’avez pas besoin de regarder le deuxième nœud de chaque liste. Vous n’avez pas besoin de parcourir toutes les listes. Il vous suffit de trouver efficacement le minimum parmi k candidats, d’avancer le pointeur de cette liste, puis de répéter. Tout le reste — heap, récursion, arbre de fusion — n’est qu’une façon de rendre cette opération rapide.
À quoi cela ressemble en pratique
Prenez trois listes : `[1→4→7]`, `[2→5→8]`, `[3→6→9]`. Le premier nœud de sortie doit être 1, qui est la tête de la liste 1. Après avoir pris 1, les candidats sont `[4]`, `[2]`, `[3]`. Le nœud suivant est 2, de la liste 2. Les candidats deviennent alors `[4]`, `[5]`, `[3]`. Puis vient 3, et ainsi de suite.
Remarquez ce qui se passe : à chaque étape, vous choisissez parmi exactement k candidats et vous faites avancer exactement un pointeur. Le nombre total de ces décisions est N (le nombre total de nœuds dans toutes les listes). Chaque décision coûte quelque chose qui dépend de k, pas de N. C’est la forme O(N log k) qui émerge directement de la structure du problème — pas de l’implémentation, mais de ce que le problème exige réellement.
Les candidats fluides le nomment avant d’écrire une seule ligne. Les candidats qui ont seulement mémorisé la fusion de deux listes se mettent à coder immédiatement, puis sont incapables d’expliquer la complexité lorsqu’on leur demande.
Faites de O(N log k) la cible, pas une estimation
Pourquoi l’intervieweur se soucie du k dans le log
O(N log k) est l’affirmation de complexité qui sépare une solution correcte d’une solution bonne. Si k apparaît dans le log, c’est parce que le heap comme l’arbre de fusion divide and conquer effectuent des opérations dont le coût dépend du nombre de listes, et non du nombre total de nœuds. Quand k est petit — disons 10 listes — log k vaut environ 3,3. Quand N vaut un million, la différence entre 3,3 millions d’opérations et un milliard est énorme. Voilà pourquoi l’intervieweur y tient. Comme l’explique Introduction to Algorithms (CLRS), la fusion k-aire avec une file de priorité atteint exactement cette borne, et c’est une référence classique pour les problèmes de sélection basés sur un heap.
À quoi cela ressemble en pratique
Voici l’argument de comptage que vous pouvez dire à voix haute. Il y a N nœuds au total. Chaque nœud est inséré exactement une fois dans le heap et retiré exactement une fois. Chaque insertion ou extraction coûte O(log k) parce que le heap ne contient jamais plus de k éléments — un par liste. Le travail total est donc N insertions × O(log k) chacune = O(N log k). Le même raisonnement s’applique au divide and conquer : il y a log k niveaux dans l’arbre de fusion (puisque vous divisez par deux le nombre de listes à chaque niveau), et chaque niveau traite chaque nœud exactement une fois, ce qui donne O(N) de travail par niveau × O(log k) niveaux = O(N log k).
Les deux stratégies arrivent au même résultat. La différence porte sur la manière d’ordonnancer le travail, pas sur la quantité de travail.
La réponse à donner quand on vous demande pourquoi pas O(Nk)
L’approche naïve — parcourir les k têtes à chaque étape pour trouver le minimum — coûte O(k) par décision sur un nœud. Avec N nœuds au total, cela donne O(Nk). Pour k=2, c’est acceptable. Pour k=1000, vous faites mille comparaisons pour extraire un seul nœud, et vous répétez cela un million de fois. La structure s’effondre dès que k grandit, ce qui est précisément le cas d’entretien où k est traité comme une variable significative.
Le heap remplace ce parcours O(k) par une opération de heap en O(log k). La mécanique supplémentaire — le heap lui-même — vaut la peine parce qu’elle échange un parcours linéaire contre un parcours logarithmique. C’est tout l’argument. Vous n’ajoutez pas de complexité pour faire élégant ; vous l’ajoutez parce que le parcours naïf est réellement plus lent quand k n’est pas trivial.
Utilisez un min heap quand vous voulez la réponse la plus nette en direct
Pourquoi la version heap est si adaptée à l’entretien
Un min-heap conserve à tout moment exactement un nœud par liste active — la tête courante. Le flot de contrôle est facile à décrire en une phrase : insérez toutes les têtes initiales, puis retirez répétitivement le minimum, ajoutez-le au résultat, et insérez le suivant de ce nœud s’il existe. Il n’y a ni appels récursifs, ni calcul d’indices, ni gestion d’arbre de fusion. Sous pression, cette simplicité vaut cher.
La version heap est aussi facile à faire confiance. Comme l’invariant du heap garantit que le minimum est toujours au sommet, vous n’avez jamais à vous demander si vous auriez pu manquer un nœud plus petit quelque part. La structure de données fait ce raisonnement pour vous.
À quoi cela ressemble en pratique
Commencez avec trois listes chaînées : `1→4→7`, `2→5→8`, `3→6→9`. Initialisez le heap avec les têtes : poussez `(1, node_1_4_7)`, `(2, node_2_5_8)`, `(3, node_3_6_9)`.
Étape 1 : retirez `(1, node)`. Ajoutez le nœud 1 au résultat. Poussez le suivant de ce nœud : `(4, node_4_7)`. Le heap contient maintenant `(2, ...)`, `(3, ...)`, `(4, ...)`.
Étape 2 : retirez `(2, node)`. Ajoutez le nœud 2. Poussez `(5, node_5_8)`. Heap : `(3, ...)`, `(4, ...)`, `(5, ...)`.
Étape 3 : retirez `(3, node)`. Ajoutez le nœud 3. Poussez `(6, node_6_9)`. Et ainsi de suite.
La taille du heap ne dépasse jamais k. Chaque nœud est inséré une fois et retiré une fois. La chaîne fusionnée se construit correctement parce que vous ajoutez toujours le minimum global. C’est le dry run que vous devez pouvoir raconter sans regarder votre code.
Le petit problème agaçant de Python avec le heap
`heapq` en Python compare les tuples de gauche à droite. Si deux nœuds ont la même valeur, il essaie de comparer directement les objets `ListNode` — et comme `ListNode` n’implémente pas `__lt__`, cela lève une `TypeError`. La solution consiste à utiliser un tuple à trois éléments : `(node.val, index, node)`, où `index` est l’indice de la liste (de 0 à k-1). Comme les indices sont uniques, la comparaison n’atteint jamais l’objet `ListNode`.
D’après la documentation Python de heapq, les éléments du heap sont comparés selon les règles standard de comparaison de Python, ce qui signifie que tout élément servant à départager les égalités doit être comparable. L’indice fournit cette garantie proprement.
L’autre piège : les listes nulles. Si une liste d’entrée est `None` ou vide, l’insérer risque soit de provoquer un crash, soit de corrompre silencieusement votre heap. Filtrez-les avant l’initialisation. Cela prend deux lignes et vous évite une erreur d’exécution qui ressemble à une erreur logique.
Chaque nœud est inséré une fois, retiré une fois. L’indice `i` départage les égalités sans toucher à l’objet nœud.
Traitez le divide and conquer comme la même idée, simplement mieux organisée
Pourquoi l’arbre de fusion n’est pas une astuce différente
La fusion divide and conquer est le même travail de fusion k-aire, simplement ordonnancé autrement. Au lieu d’un heap qui suit dynamiquement la frontière, vous faites des paires de listes, vous les fusionnez, puis vous fusionnez les résultats, et ainsi de suite jusqu’à n’avoir plus qu’une seule liste. La structure que vous construisez est un arbre binaire de fusion équilibré, et la profondeur de cet arbre est log k — exactement le même log k qui apparaît dans la complexité du heap.
L’idée clé est que chaque fusion de deux listes coûte O(n₁ + n₂), où n₁ et n₂ sont les tailles des deux listes fusionnées. À chaque niveau de l’arbre, le travail total de toutes les fusions est O(N), parce que chaque nœud participe à une seule fusion à ce niveau. Avec log k niveaux, le travail total est O(N log k). L’analyse de merge sort dans CLRS donne la même structure de récurrence — ici, c’est merge sort appliqué à k listes au lieu de k éléments.
À quoi cela ressemble en pratique
Avec huit listes, le premier tour produit quatre listes fusionnées. Le deuxième en produit deux. Le troisième en produit une. Trois tours = log₂(8) = 3 niveaux. Chaque niveau traite tous les N nœuds une fois. L’arbre est équilibré par construction si vous faites toujours les paires de l’extérieur vers l’intérieur (liste 0 avec liste 1, liste 2 avec liste 3, et ainsi de suite), ce qui maintient des tailles de listes approximativement égales d’un tour à l’autre.
Avec quatre listes de tailles 3, 3, 3, 3 : le premier tour fusionne en deux listes de taille 6, le deuxième en une liste de taille 12. Nombre total de comparaisons : 6 + 6 + 12 = 24 = 12 × 2 = N × log k. Le calcul tient. Chaque étape de fusion préserve l’ordre trié parce que la fusion de deux listes triées est correcte par induction, et chaque niveau ne touche chaque nœud qu’une seule fois.
Quand cette explication paraît plus intelligente en entretien
Le divide and conquer est plus propre si l’intervieweur parle explicitement de récursion, s’il veut discuter de parallélisation (chaque paire peut être fusionnée indépendamment), ou s’il teste votre intuition de merge sort. C’est aussi la meilleure réponse si l’intervieweur demande : « et si vous deviez faire ça dans un système distribué ? » — l’arbre de fusion se mappe directement sur une opération de réduction (reduce) entre plusieurs workers.
La réponse avec heap est plus rapide à implémenter. La réponse divide and conquer est souvent plus facile à défendre conceptuellement, parce que l’arbre de fusion est quelque chose que vous pouvez dessiner au tableau en 10 secondes et montrer du doigt pendant que vous expliquez la complexité.
Choisissez heap ou divide and conquer comme quelqu’un qui l’a déjà fait
La matrice de décision que les intervieweurs respectent vraiment
Le choix ne porte pas sur l’approche objectivement meilleure — en complexité, elles sont équivalentes. Il s’agit de savoir laquelle vous pouvez implémenter correctement et expliquer clairement dans le temps imparti.
Utilisez un min-heap lorsque : vous êtes en Python et voulez utiliser `heapq` directement, l’entretien est un exercice de live coding où la simplicité réduit les bugs, ou l’intervieweur n’a pas parlé de récursion. La version heap est plus courte, plus linéaire dans sa structure et plus facile à suivre lors d’un dry run.
Utilisez divide and conquer lorsque : l’intervieweur mentionne la récursion, merge sort ou des solutions structurées en arbre ; lorsqu’il pose des questions sur la parallélisation ou le traitement distribué ; ou lorsque vous êtes dans un langage où la récursion est idiomatique et où les bibliothèques de heap sont moins ergonomiques. L’explication par arbre de fusion fonctionne aussi souvent mieux dans les sujets proches du system design, où l’on a l’habitude du vocabulaire reduce.
À quoi cela ressemble en pratique
Dans un entretien téléphonique en Python : commencez par le heap. Dites : « Je vais utiliser un min-heap pour suivre la tête courante de chaque liste, ce qui me donne O(N log k) sans avoir besoin de récursion. » Codez. Terminé.
Dans un entretien au tableau où l’intervieweur dessine un arbre : orientez-vous vers divide and conquer. « On peut aussi voir ça comme un arbre de fusion — on regroupe les listes par paires, on fusionne chaque paire, on recommence. Même O(N log k), et cela s’aligne proprement sur l’arbre que vous avez dessiné. »
S’il vous demande quelle approche vous préférez : « Le heap est plus rapide à implémenter en Python. Le divide and conquer est plus simple à expliquer visuellement et s’étend naturellement à une fusion parallèle. Les deux sont correctes — je choisirai celle qui convient au contexte. » Cette réponse est plus impressionnante qu’une fausse certitude.
L’erreur qui paraît assurée mais ne l’est pas
Dire « le heap est toujours meilleur » ou « le divide and conquer est plus propre » sans nuance montre que vous avez mémorisé une préférence, pas développé un jugement. Les intervieweurs qui connaissent bien ce problème vont immédiatement tester l’affirmation — « et si k est très grand ? et si les listes sont sur des machines séparées ? » — et une préférence apprise par cœur n’aura pas de réponse.
La version honnête est la suivante : les deux approches résolvent le même problème avec la même complexité, et le bon choix dépend du contexte de l’entretien, du langage et de ce que l’intervieweur cherche réellement à tester. Cette réponse est plus difficile à formuler, et c’est celle qui gagne le respect.
Codez sans tomber dans les pièges habituels
Les pièges des listes nulles et des valeurs dupliquées
Avant d’écrire une seule ligne de code pour fusionner k listes chaînées triées, posez-vous trois questions : une liste peut-elle être `None` ? Une liste peut-elle être vide (un pointeur non nul vers rien) ? La même valeur peut-elle apparaître dans plusieurs listes ?
Les listes nulles font planter l’initialisation du heap si vous les poussez sans vérification. Les listes vides sont une variante plus subtile — le pointeur existe, mais `node` est falsy. Les deux doivent être filtrées avant l’initialisation du heap. Les valeurs dupliquées ne sont pas un bug — elles se fusionnent correctement — mais elles déclenchent le problème de comparaison en Python décrit plus haut si vous n’utilisez pas l’indice de départage.
À quoi cela ressemble en pratique
Le mode d’échec sans indice de départage : deux nœuds de valeur 5 provenant de listes différentes. Python retire le premier, pousse son suivant (valeur 7), puis tente de comparer le `(5, ListNode)` restant avec `(7, ListNode)`. Les valeurs sont différentes, donc il n’atteint jamais la comparaison des nœuds — tout va bien. Mais si un autre 5 arrive plus tard, il compare `(5, ListNode)` avec `(5, ListNode)` et plante. L’indice dans le tuple évite complètement cela : `(5, 0, node)` contre `(5, 2, node)` se départage sur l’indice, jamais sur le nœud.
La version propre réutilise directement les nœuds — `tail.next = node` — au lieu d’en créer de nouveaux. C’est correct tant que vous récupérez `node.next` avant de réaffecter `tail`. L’invariant en un passage : `tail` pointe toujours vers le dernier nœud de la chaîne fusionnée, et rien derrière lui ne garde de pointeur parasite.
L’état d’esprit en un passage qui garde les pointeurs sains
Chaque nœud est inséré dans le heap une seule fois et retiré une seule fois. Quand vous retirez un nœud et faites `tail.next = node`, ce nœud fait désormais partie de la chaîne fusionnée. Quand vous poussez `node.next`, vous mettez en file le prochain candidat de cette liste. Le seul pointeur que vous faites avancer est `tail` — vous le déplacez vers le nœud que vous venez d’ajouter. Rien d’autre ne change.
L’invariant : à chaque étape de la boucle, `dummy.next` est la tête d’une chaîne correctement fusionnée se terminant par `tail`, et le heap contient exactement les têtes courantes de toutes les listes non épuisées. Si cet invariant est vrai au début de chaque itération, il reste vrai à la fin. Chaque nœud est inséré une fois, retiré une fois, ajouté une fois.
Dites le assez clairement pour que l’intervieweur cesse de vous interrompre
La réponse de 20 secondes
Voici la version orale : « C’est un problème de fusion k-aire. À chaque étape, le prochain nœud de sortie est le minimum parmi les têtes courantes des k listes. Je vais utiliser un min-heap pour suivre ces têtes efficacement, ce qui donne O(log k) par extraction et O(N log k) au total. Je traiterai les listes nulles avant d’initialiser le heap et j’utiliserai un indice de départage en Python pour éviter les erreurs de comparaison sur des valeurs égales. »
C’est tout. Trente secondes, et cela couvre le schéma, l’approche, la complexité et les cas limites. L’intervieweur sait maintenant que vous comprenez le problème avant même que vous n’ayez écrit une seule ligne.
À quoi cela ressemble en pratique
Une bonne ouverture pour expliquer la fusion de k listes triées en entretien : « Avant de coder, je veux m’assurer d’avoir bien compris les contraintes. Certaines listes d’entrée peuvent-elles être nulles ou vides ? Y a-t-il des valeurs dupliquées entre les listes ? Et la réutilisation des nœuds en place est-elle acceptable, ou souhaitez-vous allouer de nouveaux nœuds ? »
Ces trois questions prennent 10 secondes et montrent que vous avez réfléchi au problème au-delà du cas nominal. Ensuite : « Parfait. Je vais partir sur une approche par min-heap. Je pousserai la tête de chaque liste non nulle dans le heap sous forme de tuple (valeur, indice, nœud) pour gérer les égalités, puis je retirerai le minimum, l’ajouterai au résultat et pousserai son successeur s’il existe. Cette solution est en O(N log k) en temps et O(k) en espace pour le heap. »
Puis vous codez. Vous ne demandez pas la permission de commencer. Vous commentez brièvement pendant l’écriture, mais vous ne vous arrêtez pas pour expliquer chaque ligne.
Quand on vous pousse à justifier votre choix
La réponse qui résiste à la pression : « Le heap est le bon choix ici parce qu’il garde l’implémentation linéaire et l’invariant facile à vérifier — le heap contient toujours au plus k éléments, donc chaque opération coûte O(log k), et nous en faisons exactement N. Si vous vouliez discuter de l’approche divide and conquer, je peux aussi la détailler — elle atteint la même borne O(N log k) via un arbre de fusion, et elle se parallélise souvent plus facilement. Mais pour une implémentation sur une seule machine en Python, le heap est plus simple à réussir sous pression. »
Cette réponse défend le choix sans écarter l’alternative, et elle revient ensuite à O(N log k) — là où l’attention de l’intervieweur doit se porter.
Les meilleurs candidats annoncent la complexité avant qu’on la leur demande. Les plus faibles attendent la question, puis donnent un chiffre sans justification. La différence n’est pas la connaissance — c’est l’habitude d’expliquer en codant, pas après.
Comment Verve AI peut vous aider à préparer votre entretien sur la fusion de k listes triées
Le problème structurel de la préparation à cette question, c’est que lire des comparaisons entre heap et divide and conquer ne développe pas la compétence réellement testée en entretien — dire l’explication de 20 secondes à voix haute, sous pression, à quelqu’un qui va rebondir dessus. Vous pouvez lire tous les tutoriels du monde et rester muet quand l’intervieweur demande « pourquoi pas O(Nk) ? » si vous n’avez jamais eu à répondre à cette question en temps réel.
Verve AI Interview Copilot est conçu pour combler בדיוק cet écart. Il écoute en temps réel votre réponse orale, voit ce que vous dites réellement plutôt que ce que vous aviez prévu de dire, et réagit précisément à ce qui a dérapé — pas à une grille générique. Si vous expliquez correctement le heap mais butez sur la justification de la complexité, Verve AI Interview Copilot détecte immédiatement cette lacune, et non après coup. Si votre explication de 20 secondes dure deux minutes, il le relève aussi.
La pratique qui aide vraiment, ce n’est pas de relire l’algorithme — c’est de faire le dry run à voix haute, en décrivant les opérations push et pop du heap sur trois listes chaînées, puis de défendre O(N log k) quand on vous contredit. Verve AI Interview Copilot organise des simulations d’entretien qui reproduisent cette pression sans qu’il soit nécessaire de trouver un partenaire humain disponible à 23 h la veille de votre entretien. Utilisez-le pour répéter l’explication orale jusqu’à ce que l’argument de complexité sorte proprement, sans notes.
Conclusion
La question n’a jamais consisté à savoir si vous savez écrire un heap. L’entretien sur la fusion de k listes triées teste votre capacité à reconnaître une fusion k-aire, à choisir entre deux stratégies valides et à défendre ce choix dans le temps qu’il faut à l’intervieweur pour décider s’il va approfondir ou passer à autre chose.
La décision n’est pas compliquée une fois intégrée : heap quand vous voulez une implémentation propre et linéaire ainsi qu’un codage rapide ; divide and conquer quand l’intervieweur veut de la récursion, un raisonnement par arbre de fusion ou une logique de parallélisation. Les deux aboutissent à O(N log k). Les deux se défendent. La seule mauvaise est celle que vous ne pouvez pas expliquer.
Avant votre prochain entretien, faites deux choses. Répétez l’explication de 20 secondes — schéma, approche, complexité, cas limites — jusqu’à ce qu’elle vienne naturellement. Puis faites un dry run au niveau des pointeurs sur trois listes chaînées, en commentant à voix haute chaque opération push et pop du heap. Si vous pouvez faire ces deux choses sans notes, vous êtes prêt. Si vous bloquez, c’est cela qu’il faut corriger — pas le code, l’explication.
Verve AI
Archives