Liste de sauts : voies express et tirages de pièces (entretien de codage avec un ingénieur en IA)

La liste à sauter, depuis les premiers principes. Vous prenez un train qui s'arrête à chaque gare et votre arrêt est loin sur la ligne. En clair : triez les nombres et trouvez, ajoutez ou supprimez rapidement l'un d'entre eux. Une liste chaînée triée s'insère facilement mais recherche un nœud à la fois, et un tableau trié recherche rapidement mais se déplace à chaque insertion. La liste de saut empile les voies express clairsemées sur une liste chaînée triée : la recherche commence en haut à gauche, se déplace vers la droite lorsque la clé suivante n'est pas trop grande et laisse tomber une voie lorsqu'elle dépasse, et un tirage au sort donne à chaque nouvelle clé sa hauteur afin qu'il n'y ait pas de rééquilibrage. Nous retraçons une recherche de cinquante-deux en cinq étapes contre neuf, une recherche absente en six étapes contre dix et une insertion de trente-cinq avec un tirage au sort qui divise une tour en deux voies. Nous voyons pourquoi cela prend environ deux log n étapes, le casse avec des pièces malchanceuses, des clés en double, des suppressions qui manquent une voie et une hauteur illimitée, et indiquons le coût honnête : journal n attendu, recherche, insertion et suppression, environ deux pointeurs par clé, et pour un million de clés avec des exécutions prédéfinies, environ vingt voies, environ trente-huit étapes en moyenne, le pire vu soixante-dix, contre une moyenne de cinq cent mille pour une liste simple. Compromis avec les arbres équilibrés, les tableaux triés et les tables de hachage, les utilisations dans les ensembles triés Redis, les tables mémoires RocksDB et LevelDB, les files d'attente et les limiteurs de débit, les analyses ordonnées, le caractère aléatoire, le comportement du cache et la page de pratique. Le troisième échelon des structures d'une base de données expédie une échelle. Conçu pour le cycle de codage des ingénieurs IA. Entraînez-vous vous-même sur le site (gratuit, fonctionne dans votre navigateur) : https://vibeengines.com/algorithm/skip-list La page dispose d'un simulateur, d'une tâche de codage avec des tests cachés, des astuces et une explication complète. Chapitres 0:00 La question : triée et rapide à trouver, ajouter, supprimer 0:50 Force brute : une liste chaînée et un tableau trié 1:19 L'idée : des voies express, à droite puis à lancer, des lancers de pièces 1:59 Traçage des recherches et une insertion via dix touches 3:02 Pourquoi pas un journal en n étapes et aucune rotation 3:34 Le casser : pièces malchanceuses, suppressions, hauteur maximale 4:21 Le code, avec état en direct 4:48 Le temps et l'espace en détail, avec un million de clés 5:53 Compromis : arbre équilibré, tableau trié, table de hachage 6:35 Où il vit dans les systèmes d'IA 7:06 Cas extrêmes : analyses, caractère aléatoire, cache, liste vide 7:45 Entraînez-vous sur les moteurs Vibe Troisième niveau des structures qu'une base de données expédie sur le site : l'arbre B, l'arbre LSM, la liste de sauts, la table des morceaux et le hachage cohérent. #skiplist #datastructures #algorithmes #redis #aiengineer #systemdesigninterview #codinginterview