跳过列表：快速通道和硬币翻转（AI 工程师编码面试）

跳过列表，来自第一原则。您乘坐的火车在每个车站都停靠，而您的车站就在线路的远处。简单地说：对数字进行排序，并快速查找、添加或删除其中任何一个。排序链表很容易插入，但一次搜索一个节点，排序数组搜索速度很快，但每次插入时都会发生变化。跳跃列表将稀疏的快速通道堆叠在排序的链表上：搜索从左上角开始，在下一个键不太大时向右移动，并在超出时丢弃一条通道，并且硬币翻转为每个新键提供了其高度，因此无需重新平衡。我们追踪了五步对九步搜索五十二人的搜索，六步对十步搜索的缺席搜索，以及通过抛硬币将一座塔拼接成两条车道的三十五人插入。我们明白为什么它需要大约两个 log n 步骤，用不幸的硬币、重复的键、错过通道和无界高度的删除来打破它，并说明诚实的成本：预期的 log n 搜索、插入和删除，每个键大约两个指针，对于带有种子的一百万个键，运行大约二十个通道，平均大约三十八步，最差看到七十步，而普通列表的平均速度是五十万。平衡树、排序数组和哈希表、Redis 排序集、RocksDB 和 LevelDB 内存表、队列和速率限制器、有序扫描、随机性、缓存行为和练习页面的使用。数据库结构的第三级是梯子。专为人工智能工程师编码轮而设计。在网站上自己练习（免费，在浏览器中运行）：https://vibeengines.com/algorithm/skip-list 该页面有一个模拟器、一个带有隐藏测试的编码任务、提示和完整的解释器。章节 0:00 问题：排序，快速查找、添加、删除 0:50 暴力破解：链表和排序数组 1:19 想法：快速通道，然后放下，硬币翻转 1:59 跟踪搜索并通过 10 个键进行插入 3:02 为什么要使用 log n 步而不进行旋转 3:34 打破它：不幸的硬币、删除、高度上限 4:21 代码，具有实时状态4:48 时间和空间的详细信息，有一百万个键 5:53 权衡：平衡树、排序数组、哈希表 6:35 它在人工智能系统中的位置 7:06 边缘情况：扫描、随机性、缓存、空列表 7:45 在 Vibe 引擎上练习 数据库在网站上提供的结构的第三级：B 树、LSM 树、跳跃列表、片段表和一致性哈希。 #skiplist #datastructs #algorithms #redis #aiengineer #systemdesigninterview #codinginterview