cswork / core skills打开 Core Skills 练习

CORE SKILLS · 36 题 · 4 种语言

把常用的数据结构和算法亲手写一遍。

不调库,亲手实现动态数组、链表、哈希表、堆、LRU 缓存、快速排序、归并排序、KMP、BFS、Dijkstra、最小生成树、并查集、字典树、线段树和树状数组,再用锁、条件变量和信号量写按序执行、哲学家就餐、有界阻塞队列和读写锁等多线程题,最后把停车场、电梯、ATM、售货机、分账、电影选座、快递柜和酒店预订这些面向对象设计(LLD)题写成能判对错的类。每题有 Python、C++、Java、Go 起始代码和固定驱动,在线判题。

线性结构3

  1. 动态数组定长存储上的扩容与缩容
  2. 单链表头尾指针、插入删除与原地反转
  3. 双端队列(环形缓冲区)环形缓冲区上的两端进出与随机访问

哈希与堆3

  1. 哈希表(拉链法)拉链法、负载因子与扩容重哈希
  2. 最小堆上浮、下沉与 Floyd 建堆
  3. LRU 缓存哈希表加双向链表的 O(1) 淘汰
  1. 二分查找:lower_bound 与 upper_bound左闭右开区间上的 lower_bound / upper_bound
  2. 快速排序Lomuto 划分与随机基准
  3. 归并排序与逆序对稳定归并,顺便数逆序对
  4. 计数排序计数、前缀和与稳定回填
  5. KMP 字符串匹配前缀函数与不回退的线性匹配

图6

  1. 网格 BFS 最短路队列逐层扩展求最少步数
  2. 拓扑排序(字典序最小)Kahn 算法、最小堆与判环
  3. Dijkstra 最短路最小堆与懒删除的单源最短路
  4. Bellman-Ford 最短路与负环负权边、n - 1 轮松弛与负环检测
  5. Kruskal 最小生成树按权排序加并查集的最小生成树
  6. Prim 最小生成树(稠密图)邻接矩阵上 O(n²) 的最小生成树

高级结构4

  1. 并查集(路径压缩 + 按秩合并)路径压缩与按秩合并
  2. 字典树(Trie)带计数的插入、删除与前缀统计
  3. 线段树:区间和与单点修改O(log n) 的区间求和与单点修改
  4. 树状数组(Fenwick Tree)lowbit、前缀和与倍增求第 k 个

并发7

  1. 按序执行两个完成信号让三个任务按序执行
  2. 交替输出两个线程严格轮流执行
  3. 零、偶、奇三个线程接力输出 0 1 0 2 …
  4. 造水分子信号量加屏障,两个氢配一个氧
  5. 哲学家就餐按编号拿叉子,打破循环等待
  6. 有界阻塞队列一把锁、两个条件变量的生产者与消费者
  7. 读写锁读者共享、写者独占,用一把锁和条件变量实现

面向对象设计(LLD)8

  1. 停车场车位分配、停车票与按小时计费
  2. 电梯调度LOOK 调度:按停靠方向分类的请求
  3. ATM 取款机状态模式、PIN 锁卡与配钞
  4. 自动售货机三态状态机、押金与贪心找零
  5. 酒店预订按晚计数的库存与周末价
  6. 分账(Splitwise)不丢一分钱的分摊与确定的结算规则
  7. 电影选座全有或全无的锁座与过期释放
  8. 快递柜格口分配、取件码与防暴力尝试