面试题库 › C++ / 后端 › 实现按 key 有序、可复用删除位置的 put

实现按 key 有序、可复用删除位置的 put

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:数据结构设计

哪些公司问过

微软1

常见岗位:软件开发(未写技术栈)

答案要点

  1. 先澄清题意:有序存储、覆盖与插入、delete 的语义
  2. 二分查找定位 key 或插入点,墓碑保留 key 以维持有序
  3. 删除只做标记,插入时若相邻位置是墓碑且不破坏有序则复用
  4. 墓碑比例过高时整体压缩,避免空间与查找退化
  5. 复杂度:查找 O(log n),复用插入 O(1),搬移插入 O(n);替代方案为平衡树

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题