Les entrevues au tableau blanc testent plus que la vitesse de résolution de problèmes. Elles évaluent la communication, la clarté et la pensée structurée. La méthode REACTO vous donne un cadre reproductible : Repeat, Examples, Approach, Code, Test, Optimize. Les interviewers veulent entendre votre raisonnement à haute voix : une démonstration propre sans réponse bat une solution bâclée sans explication.
Le problème principal
Étant donné un tableau de nombres et une somme cible, déterminer si deux nombres quelconques du tableau s'additionnent pour atteindre la cible. Retourner un booléen.
- Tableau [1, 2, 3, 9] avec somme 8 → retourne false (pas de paire valide)
- Tableau [1, 2, 4, 4] avec somme 8 → retourne true (4 + 4 = 8)
R : reformuler la question
Entrée : un tableau d'entiers et une somme cible. Sortie : un booléen, true si deux nombres s'additionnent pour atteindre la cible, false sinon.
Clarifications à aborder à haute voix :
- Retourner la paire ou juste un booléen ? → Booléen uniquement
- Les nombres peuvent-ils être négatifs ou non ordonnés ? → Oui
- Le même élément peut-il être utilisé deux fois ? → Non, ce doivent être deux indices distincts
- Que faire si le tableau est vide ou a un seul élément ? → Retourner false
E : exemples de cas
Avant de toucher au code, parcourez les exemples avec l'interviewer. Confirmez votre compréhension des cas limites : tableau vide, élément unique, doublons, négatifs. C'est là que beaucoup de candidats perdent des points en allant trop vite.
- [1, 2, 3, 9] cible 8 → false
- [1, 2, 4, 4] cible 8 → true (4 + 4)
- [-1, 5, 3] cible 4 → true (-1 + 5)
- [] cible 5 → false
- [5] cible 5 → false (besoin de deux éléments distincts)
A : approche
Force brute. O(n²)
Boucles imbriquées : pour chaque élément, vérifier chaque autre élément. Simple à expliquer mais ne passe pas à l'échelle. Mentionnez ça d'abord : les interviewers apprécient de savoir que vous comprenez la solution naïve avant d'optimiser.
Optimisé. HashSet O(n)
Utiliser un Set pour traquer les nombres vus jusqu'ici. Pour chaque élément, calculer son complément (cible moins courant). Si le complément est déjà dans le Set, une paire valide existe. Sinon, stocker le nombre courant et continuer. Un seul passage dans le tableau, recherche O(1) par étape.
C : code
function hasPairWithSum(arr: number[], sum: number): boolean {
const seen = new Set<number>();
for (const num of arr) {
const complement = sum - num;
if (seen.has(complement)) {
return true;
}
seen.add(num);
}
return false;
}
console.log(hasPairWithSum([1, 2, 3, 9], 8)); // false
console.log(hasPairWithSum([1, 2, 4, 4], 8)); // true
console.log(hasPairWithSum([-1, 5, 3], 4)); // trueT : tester votre solution
Tracez l'algorithme manuellement avec [1, 2, 4, 4], sum=8 :
- num=1 : complement=7, pas dans seen. Ajouter 1. seen={1}
- num=2 : complement=6, pas dans seen. Ajouter 2. seen={1,2}
- num=4 : complement=4, pas dans seen. Ajouter 4. seen={1,2,4}
- num=4 : complement=4, EST dans seen → return true
Maintenant testez un cas limite : tableau vide. La boucle ne s'exécute jamais, retourne false. Un seul élément [5] avec sum 10 : une itération, complement=5, seen est vide, ajoute 5, boucle terminée, retourne false. Comportement correct.
O : optimiser et discuter des compromis
La solution HashSet est déjà O(n) en temps et O(n) en espace. Si l'interviewer demande de réduire l'espace : un tableau trié avec deux pointeurs atteint O(n log n) en temps et O(1) en espace supplémentaire, mais seulement si le tri se fait en place. Array.prototype.sort dans V8 est TimSort, qui utilise O(n) de mémoire auxiliaire et modifie le tableau que vous lui passez, donc trier une copie vous ramène à O(n) en espace. Ce qui est mieux dépend des contraintes : si l'entrée est déjà triée et la mémoire est limitée, les deux pointeurs gagnent.
// Two-pointer approach (requires sorted input)
function hasPairWithSumSorted(arr: number[], sum: number): boolean {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const current = arr[left] + arr[right];
if (current === sum) return true;
if (current < sum) left++;
else right--;
}
return false;
}
// Input must be sorted
console.log(hasPairWithSumSorted([1, 2, 3, 9], 8)); // false
console.log(hasPairWithSumSorted([1, 2, 4, 4], 8)); // trueBonus : données en streaming
Un interviewer pourrait étendre le problème : et si l'entrée est un flux plutôt qu'un tableau fini ? Vous pouvez appliquer la même logique HashSet avec un générateur, mais avec une mise en garde importante : si aucune paire n'existe dans le flux, la fonction ne se termine jamais. Dans une entrevue, nommer cette limitation explicitement montre de la maturité.
function hasPairWithSumStream(
stream: Iterable<number>,
sum: number,
limit = 10_000 // guard against infinite streams with no solution
): boolean {
const seen = new Set<number>();
let count = 0;
for (const num of stream) {
if (count++ >= limit) return false; // safety exit: false here means 'not found within limit'
const complement = sum - num;
if (seen.has(complement)) return true;
seen.add(num);
}
return false;
}
// Example: finite generator
function* numberStream(values: number[]) {
for (const v of values) yield v;
}
console.log(hasPairWithSumStream(numberStream([1, 2, 4, 4]), 8)); // trueLisez ce garde-fou attentivement, car il change le sens de la fonction. Retourner false après la limite dit « aucune paire n'existe », alors que tout ce que le code sait, c'est « aucune paire dans les 10 000 premières valeurs ». C'est un faux négatif, et c'est la moitié la plus intéressante du compromis. Si l'appelant doit distinguer les deux cas, retournez trois états plutôt qu'un booléen : trouvé, non trouvé, limite atteinte. Nommer ce que votre sortie de sécurité vous coûte vaut plus en entrevue que le garde-fou lui-même.
Concepts clés à connaître parfaitement
Set : stocke des valeurs uniques avec des opérations add et has en O(1) en moyenne, et dites « en moyenne » à voix haute, parce que le hachage se dégrade dans le pire cas. Plus efficace qu'un tableau pour les vérifications d'appartenance. La structure de données clé derrière cette solution.
for...of : itère sur tout itérable (tableau, Set, sortie de générateur). Pas de gestion d'index nécessaire, fonctionne proprement avec les générateurs.
Fonctions génératrices : mettent en pause et reprennent l'exécution avec yield. Retournent un itérateur qui produit des valeurs à la demande. Utiles pour simuler des flux ou des séquences paresseuses. Le point clé en entrevue : les générateurs sont paresseux, mais s'il n'y a pas de condition de terminaison et que le problème n'a pas de solution, l'itération ne s'arrête jamais.
En entrevue, la qualité de votre explication a autant de valeur que l'exactitude de votre code. Parcourez l'algorithme étape par étape, testez votre propre solution à haute voix, et nommez les compromis avant que l'interviewer ne les demande.
Références
- MDN Web Docs. Set. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
- MDN Web Docs. Iterators and Generators. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_generators
- LeetCode. Two Sum (classic variant). https://leetcode.com/problems/two-sum/
- GeeksforGeeks. Two Sum, Pair with Given Sum. https://www.geeksforgeeks.org/dsa/check-if-pair-with-given-sum-exists-in-array/