Available inFrenchEnglishGermanHindiPortugueseRussianSpanish
Patterns d'entretien de code (Blind 75)
Lisez un problème inédit de la Blind 75, nommez la technique qu'il appelle et l'invariant qui la rend correcte, avant d'écrire une ligne de code. Pour qui a déjà résolu soixante-dix problèmes LeetCode ou plus et se bloque encore devant un énoncé jamais vu ; le Big-O est acquis, la syntaxe n'est pas enseignée. Soixante-quatre cartes relient dix familles de techniques aux problèmes qui les demandent.
Tableau trié, deux éléments dont la somme vaut une cible, O(1) d'espace en plus. Quelle technique cet énoncé désigne-t-il ?
Two pointers convergents, un à chaque bout
— Le tri fait ici le travail qu'une hash map ferait sinon.
Source
Trois indices se combinent : l'entrée arrive triée, la réponse est une paire, et la borne d'espace interdit la hash map. Un indice à chaque bout ; si la somme est trop grande le droit recule, trop petite le gauche avance. Chaque pas retire un indice pour de bon, donc le balayage est en O(n) sans mémoire ajoutée. Le nom se dit tel quel dans la salle, « two pointers » ; le calque « deux pointeurs » sert à comprendre, pas à répondre. Souvent confondu avec : la hash map en une passe, la bonne réponse quand le tableau n'est pas trié et que l'espace est libre, puisque trier d'abord coûterait un O(n log n) inutile ici.