Plus longue séquence consécutive et cache LRU

LeetCode 128 « Plus longue séquence consécutive » : étant donné un tableau non trié, trouvez la longueur de la plus longue séquence d’entiers consécutifs. Exemple : [100,4,200,1,3,2] contient la séquence consécutive [1,2,3,4], de longueur 4. La difficulté consiste à résoudre le problème en O(n) plutôt qu’en O(n log n), complexité obtenue avec un tri suivi d’un parcours.

L’idée essentielle est d’utiliser un ensemble pour effectuer des tests d’appartenance en O(1), et de commencer à compter une séquence uniquement à partir de son plus petit élément (identifié en vérifiant que son prédécesseur est absent de l’ensemble).

Chaque nombre est parcouru au plus une fois dans la boucle tant que, sur l’ensemble des itérations de la boucle externe. Même si une boucle tant que se trouve à l’intérieur d’une boucle pour, le nombre total d’itérations de la boucle tant que sur toutes les itérations externes est au plus égal à n (car chaque nombre est le « curr_n + 1 » d’au plus une séquence). Cet argument amorti donne une complexité globale de O(n), comme dans l’analyse de la pile monotone.

En comparaison, l’approche consistant à trier puis à parcourir s’exécute en O(n log n) : triez le tableau, éliminez les doublons consécutifs, puis comptez les séquences consécutives. Bien qu’elle soit plus lente, elle utilise un espace supplémentaire de O(1) (si le tri est effectué en place). L’approche avec un ensemble utilise un espace supplémentaire de O(n). Présentez les deux méthodes lors d’un entretien et précisez si la solution en O(n log n) est acceptable compte tenu des contraintes d’espace.

Un cache LRU (élément utilisé le moins récemment) est une structure de données à capacité fixe qui expulse l’élément utilisé le moins récemment lorsqu’il est plein et qu’un nouvel élément doit être inséré. Opérations : get(key) renvoie la valeur si la clé existe (et la marque comme récemment utilisée), ou -1 si elle est absente ; put(key, value) insère la paire (en expulsant l’élément LRU si la capacité est atteinte).

Les caches LRU sont utilisés dans les systèmes d’exploitation (remplacement de pages), les caches des navigateurs et les caches de requêtes de bases de données. LeetCode 146 vous demande d’en implémenter un avec des opérations get et put en O(1).

Le collections.OrderedDict de Python conserve l’ordre d’insertion et prend en charge move_to_end(key) (en O(1)) pour marquer un élément comme le plus récemment utilisé. Lors d’un put, déplacez la clé à la fin ; en cas de dépassement de capacité, retirez le premier élément (LRU). Vous obtenez ainsi des opérations get et put en O(1) grâce à une fonctionnalité intégrée qui repose en interne sur une liste doublement chaînée et une table de hachage.

L’implémentation construite à partir de zéro utilise une liste doublement chaînée (pour permettre la suppression d’un nœud en O(1)) et une table de hachage (pour rechercher un nœud par sa clé en O(1)). La liste conserve l’ordre du LRU (head.next) au MRU (tail.prev). Les sentinelles factices de tête et de queue éliminent les cas particuliers lors de l’insertion et de la suppression aux extrémités.

Une liste simplement chaînée ne peut pas supprimer un nœud arbitraire en O(1) sans connaître son prédécesseur. Une liste doublement chaînée stocke les deux pointeurs prev et next, ce qui permet une suppression en O(1) lorsque la référence du nœud est connue. La table de hachage fournit un accès au nœud par sa clé en O(1). Ensemble : get(key) prend O(1) pour trouver le nœud et O(1) pour le déplacer vers la queue ; put(key) prend O(1) pour ajouter un élément et O(1) pour supprimer le nœud LRU de la tête.

Une variante plus difficile est le cache LFU (LeetCode 460), dans lequel l’élément ayant le plus petit nombre d’accès est expulsé. En cas d’égalité, la récence départage les éléments (le moins récemment utilisé parmi ceux qui sont les moins fréquents). L’implémentation nécessite trois structures de données : une table clé-valeur, une table clé-fréquence et une table fréquence-vers-OrderedDict (pour conserver l’ordre d’insertion au sein de chaque groupe de fréquences). Les opérations get et put de LFU sont en O(1) amorti.

Le cache LRU illustre un schéma de conception puissant : combiner une table de hachage pour rechercher une clé en O(1) avec une liste chaînée pour effectuer des opérations ordonnées en O(1). Ce schéma apparaît dans plusieurs problèmes de conception posés en entretien : cache LRU, cache LFU, listes à raccourcis et certaines variantes de files. Chaque fois qu’un problème exige à la fois une recherche en O(1) et des opérations fondées sur l’ordre en O(1), envisagez cette combinaison.

Lors des entretiens, énoncer explicitement ce schéma démontre une capacité de raisonnement à l’échelle du système et une bonne connaissance des combinaisons classiques de structures de données.

Il s’agit d’une extension de l’idée de séquence consécutive en deux dimensions : étant donné une matrice d’entiers, trouvez la longueur de la plus longue séquence consécutive pouvant être suivie (chaque étape se déplace vers une cellule adjacente). Cette approche combine BFS/DFS avec l’approche par ensemble pour les séquences consécutives. Stockez la position de chaque valeur, puis, pour chaque valeur de départ, vérifiez si value+1 existe comme voisin.

Ces deux problèmes ont un thème commun : transformer des problèmes en O(n log n) ou O(n²) en problèmes en O(n) grâce à la structure de hachage appropriée. La plus longue séquence consécutive utilise un ensemble pour répondre à la question « le prédécesseur est-il présent ? » en O(1). Le cache LRU utilise une table de hachage pour trouver instantanément le nœud et une liste doublement chaînée pour mettre à jour l’ordre en O(1). Les deux remplacent un parcours lent par un test d’appartenance ou une recherche en O(1).

Lorsqu’un recruteur vous demande « pouvez-vous faire mieux que O(n log n) ? », la réponse est presque toujours : « utilisez une table de hachage ou un ensemble de hachage pour éviter le tri ».

Dans cette leçon, vous avez appris : la plus longue séquence consécutive s’exécute en O(n) grâce à un ensemble permettant des tests d’appartenance en O(1) et au fait de ne commencer le comptage qu’au début des séquences, le cache LRU atteint O(1) pour get et put avec un OrderedDict (ou avec une table de hachage et une liste doublement chaînée construite à partir de zéro), et le schéma table de hachage + liste chaînée est un composant réutilisable pour les structures de données en O(1) sensibles à l’ordre. Ensuite, nous reviendrons à la récursivité avec le cadre du cas de base, de la confiance et de la construction.