假设有一个包含10万道题的题库，每道题有难度、类型、知识点等标签。用户需要根据多个条件（如难度在10-15之间，类型为几何，知识点包含三角形）进行检索。请设计一个高效检索算法，并分析时间复杂度。

1) 【一句话结论】：采用倒排索引（标签-题目ID列表映射）实现多条件检索，通过标签快速定位题目并求交集，时间复杂度约为O(k)，远优于线性扫描的O(n)（n=10万）。

2) 【原理/概念讲解】：核心是倒排索引。将每个标签（如“难度10-15”“几何”“三角形”）作为键，值是包含该标签的所有题目ID列表。检索时，对每个查询条件（标签），查询对应的ID列表，再求这些列表的交集，得到符合条件的题目ID。类比：图书馆的索引卡，每个主题（标签）对应所有包含该主题的书籍（题目），检索时查多个主题的交集，快速找到相关书籍，避免逐本翻找。

3) 【对比与适用场景】：

方法	定义	特性	使用场景	注意点
线性扫描	遍历所有题目，逐个检查标签	时间复杂度O(n)，n=10万	标签数量少，条件简单	高效性差，不适合多条件检索
倒排索引	标签→题目ID列表映射	时间复杂度O(k)，k=标签数	多条件、高频检索	需额外空间存储索引
哈希表	标签→哈希值→题目ID	平均时间O(1)，空间O(n)	标签唯一，快速单条件检索	标签冲突或重复导致性能下降
B树/平衡树	标签排序+树结构	时间复杂度O(log n)	标签有序，范围查询（如难度范围）	维护成本高

4) 【示例】：伪代码

• 构建索引：

  # 题目结构：id, tags（列表，如["难度12", "类型几何", "知识点三角形"]）
  index = {}  # 标签: [题目id列表]
  for 题目 in 题库:
      for tag in 题目.tags:
          if tag not in index:
              index[tag] = []
          index[tag].append(题目.id)
  

• 检索函数：

  def search(conditions):
      result_ids = None
      for tag in conditions:
          if tag not in index:
              return []  # 无匹配
          current_ids = index[tag]
          if result_ids is None:
              result_ids = current_ids
          else:
              # 求交集
              result_ids = list(set(result_ids) & set(current_ids))
      return result_ids
  

  示例：检索条件为难度10-15、类型几何、知识点三角形，结果为同时满足三个标签的题目ID列表。

5) 【面试口播版答案】：面试官您好，针对10万道题的题库，多条件检索，核心思路是用倒排索引。具体来说，就是为每个标签（难度、类型、知识点）建立一个列表，记录所有包含该标签的题目ID。检索时，对每个条件标签，查询对应的ID列表，然后求这些列表的交集，得到符合条件的题目。这样时间复杂度是O(k)，k是标签数量，比遍历所有题目O(10万)高效得多，特别适合多条件、高频检索场景。

6) 【追问清单】：

• 问题1：如果标签有权重（比如难度权重更高），如何调整检索结果？
  回答要点：可以给每个标签的ID列表加权（如难度标签的权重更高），在求交集后，根据权重计算综合得分，优先返回高权重的题目。
• 问题2：索引更新（如新增题目）如何处理？
  回答要点：动态维护倒排列表，插入新题目时，为每个相关标签的列表添加题目ID；删除题目时，从所有相关标签的列表中移除。
• 问题3：标签是字符串，如何支持模糊匹配（如“三角形”包含“三角”的题目）？
  回答要点：对标签字符串进行前缀匹配或部分匹配，比如在索引时存储标签的哈希或前缀，检索时匹配前缀即可。
• 问题4：多条件组合过多（如超过5个标签）时，交集效率会下降？
  回答要点：可以用B树或哈希表优化交集，比如先合并小的列表再求交集，或者分阶段处理（先过滤出符合条件的标签列表，再逐步求交集）。
• 问题5：空间复杂度如何？是否需要考虑存储成本？
  回答要点：空间复杂度为O(n*m)，n是题目数，m是平均标签数，对于10万题目，每个标签平均10个标签，空间占用约100万条记录，实际存储可压缩（如ID列表用数组存储，标签用字符串哈希）。

7) 【常见坑/雷区】：

• 坑1：直接用线性扫描，忽略标签索引，导致时间复杂度O(n)，不符合高效要求。
• 坑2：没说明索引的维护成本，比如新增题目时需要更新所有相关标签的列表，若题目数量大，更新成本高。
• 坑3：标签重复或冲突，导致索引冗余，影响空间效率。
• 坑4：没分析时间复杂度，只说“快”，但没量化（如O(k) vs O(n)）。
• 坑5：没考虑标签的排序，倒排列表是否需要排序，影响交集效率。