搜广推校招面经六十一

美团推荐算法

一、ANN算法了解么？说几种你了解的ANN算法

ANN 近似最近邻搜索（Approximate Nearest Neighbor Search）算法

1.1. KD-Tree（K-Dimensional Tree，K 维树）

• 类型: 空间划分数据结构
• 适用场景: 低维数据（通常小于 20 维）
• 原理:
  • 递归地选择某个维度的中位数进行划分，构造二叉树
  • 查询时回溯遍历最近邻点
• 优缺点:
  • 适用于 低维欧几里得空间搜索
  • 在 高维数据（>20 维） 下效率急剧下降（维度灾难）

1.2. LSH（局部敏感哈希，Locality-Sensitive Hashing）

• 类型: 基于哈希的近似最近邻搜索
• 适用场景: 高维数据、文本检索、推荐系统、图像搜索
• 原理:
  • 通过 哈希函数 将相似向量映射到相同的桶
  • 通过减少搜索空间，加速最近邻查找
• 经典方法:
  • MinHash（Jaccard 相似度，用于集合相似性计算）
  • SimHash（海量文本去重，如 Google 使用 SimHash 进行网页去重）
• 优缺点:
  • 适用于高维数据，但精度可能不如图搜索（如 HNSW）

1.3. 倒排索引（Inverted Index）

• 类型: 基于索引的搜索方法
• 适用场景: 文本检索（如搜索引擎）、稀疏向量搜索
• 原理:
  • 记录 关键词 -> 文档 ID 列表，可快速找到包含查询关键词的所有文档
  • 向量检索时可以与 HNSW（Hierarchical Navigable Small World） 结合，提高搜索效率
• 优缺点:
  • 适用于离散数据（如文本、关键词），对连续高维向量的搜索能力有限

1.4. HNSW（层次可导航小世界图，Hierarchical Navigable Small World）

• 类型: 基于图的近似最近邻搜索
• 适用场景: 高维向量检索（推荐系统、图像搜索）
• 原理:
  • 构建 小世界图（Small World Graph），通过跳跃式邻居搜索快速找到最近邻
  • 适用于 高维数据搜索，比 KD-Tree 和 LSH 更快、更精确
• 优缺点:
  • 性能远优于 KD-Tree 和 LSH，适用于 超高维数据搜索
  • 需要 较大的内存 来存储索引

1.5. FAISS（Facebook AI Similarity Search）

• 类型: 高维向量搜索库
• 适用场景: 图像检索、语音检索、推荐系统
• 原理:
  • 支持 PQ（Product Quantization）、IVF（Inverted File Index）、HNSW 等多种索引方法
  • 适用于 大规模向量搜索（如 十亿级别的向量数据库）
• 优缺点:
  • 大规模向量搜索最优选择
  • 需要 GPU 加速才能发挥最大效能

1.6. 推荐工具

• FAISS（Facebook AI）: 适用于 GPU 加速的向量搜索
• Annoy（Spotify）: 适用于内存受限的情况，构建高效 KD-Tree
• HNSWlib: 纯 C++ 实现的高效 HNSW 近似最近邻搜索

二、推荐算法 vs. 广告算法的区别

推荐算法（Recommendation Algorithm）和广告算法（Advertising Algorithm）在 目标、数据输入、优化目标、应用场景 等方面有较大不同，两者都涉及 个性化推荐 和 用户行为预测

2.1. 核心目标

	推荐算法	广告算法
核心目标	提高用户体验，增加用户粘性，提升内容消费	提高广告转化率（CTR、CVR），优化广告收益
优化目标	让用户更喜欢和更长时间停留在平台	让广告主的投放 ROI 最大化，提高收益

2.2. 算法模型

	推荐算法	广告算法
主流方法	协同过滤（CF）、矩阵分解、深度学习（DNN、Transformer）、强化学习	逻辑回归（LR）、GBDT、深度CTR模型（Wide & Deep、DeepFM、Transformer-based CTR）
目标优化	召回 + 排序	预估 CTR/CVR + 竞价优化
在线/离线	大部分离线训练，部分在线更新	在线实时计算，多轮竞价

2.3. 核心流程

推荐算法流程

1. 召回阶段（候选生成）：快速筛选可能感兴趣的内容
   • 基于协同过滤、用户兴趣模型、内容相似性等方法
2. 粗排阶段：初步排序，过滤低质量内容
   • 轻量级模型（如 GBDT、Embedding-based 方法）
3. 精排阶段：更复杂的深度学习模型（DNN、Transformer）
   • 预测用户点击率、停留时间、互动行为等
4. 重排序 & 多目标优化：
   • 结合用户体验、平台收益、内容多样性等

广告算法流程

1. 广告召回：
   • 召回匹配的广告（基于用户历史、关键词、兴趣等）
2. CTR/CVR 预估：
   • 预测该广告被点击（CTR）和转化（CVR）的概率
3. eCPM 计算：
   • eCPM = 预估点击率 × 出价
   • 计算每个广告对平台的潜在收益
4. 广告竞价：
   • 竞价策略（如 Vickrey-Clarke-Groves 机制）
   • 选择收益最高的广告展示

三、召回模型中的负样本选择：为什么要负采样？

在推荐系统的召回阶段，我们通常使用 监督学习 来训练模型，而监督学习需要 正样本（用户感兴趣的物品） 和 负样本（用户不感兴趣的物品）。由于真实世界中 负样本远多于正样本，因此需要 负采样（Negative Sampling） 来提升训练效率和模型效果。

3.1. 为什么要进行负采样？

3.1.1 计算资源限制

• 真实世界中，未点击的物品数量 远超已点击的物品，直接使用所有未点击的物品作为负样本，会导致 数据量过大，计算成本极高。
• 负采样可以 减少训练数据量，降低计算复杂度，提高训练速度。

3.1.2 训练效果优化

• 如果将 所有未交互的物品 作为负样本，容易导致数据 极度不均衡，模型可能会学习到 “不点击才是常态”，从而忽略正样本信息。
• 通过 合理的负采样策略，可以选取更具代表性的负样本，使模型更准确地学习用户的偏好。

3.1.3 解决数据偏差问题

• 在推荐系统中，用户未点击的内容并不一定是他们不感兴趣的（可能是 未曝光）。
• 直接将所有未点击的物品视为负样本可能会引入噪声，而负采样可以帮助过滤掉这些噪声。

3.2. 常见的负采样方法

3.2.1. 随机负采样（Random Negative Sampling）

• 方法：随机从未交互物品池中选择一定数量的物品作为负样本。
• 优点：简单易实现，计算成本低。
• 缺点：可能采样到无意义的负样本（如用户从未接触过的类别），影响训练效果。

3.2.2. 基于流行度的负采样（Popularity-based Negative Sampling）

• 方法：按照物品的流行度（如点击量、购买量）进行采样，越流行的物品被选中的概率越高。
• 优点：增加热门物品作为负样本，提高模型对流行趋势的学习能力。
• 缺点：可能导致模型偏向推荐热门物品，影响长尾物品的推荐效果。

3.2.3. 硬负采样（Hard Negative Sampling）

• 方法：选择 与用户历史兴趣最相似但未被点击 的物品作为负样本。例如，基于 Embedding 相似度 或 模型预测分数最高但未实际交互 的物品进行采样。
• 优点：
  • 负样本质量高，提高模型的判别能力。
  • 可以更好地区分 “用户可能感兴趣但未点击” 和 “用户完全不感兴趣” 的内容。
• 缺点：
  • 计算成本较高，需要额外的相似度计算或预训练模型。

四、什么是哈利波特效应 和 新闻联播效应

4.1. 哈利波特效应

概念

• “哈利波特效应”（Harry Potter Effect）指的是 头部效应，即 极少数头部内容获得大量关注，而长尾内容则难以被发现。
• 这种现象广泛存在于 图书、电影、音乐、短视频、游戏等文娱产业，表现为 爆款作品 迅速吸引大部分用户的注意力，而其他内容则被冷落。

原因

• 马太效应（强者愈强，弱者愈弱）：热门作品的知名度越高，越容易获得额外流量。
• 社交传播效应：热门内容容易被社交媒体讨论和推荐，形成病毒式传播。
• 平台推荐机制：算法倾向于推荐已有较高互动的内容，进一步放大头部效应。

影响

• 头部效应强化：资源和流量向头部内容集中，少量爆款内容占据市场大部分收益。
• 长尾内容难以崛起：中小创作者、独立作品难以获得曝光，导致内容多样性下降。
• 用户兴趣趋同：用户接触的信息可能变得越来越相似，难以发现个性化内容。

典型案例

• 哈利·波特系列图书：全球畅销，形成现象级 IP，而其他同类奇幻小说难以获得类似的市场份额。
• 抖音/B站爆款视频：少数高播放量的视频获得大量推荐和转发，而大部分普通创作者的视频很难出圈。
• 好莱坞电影：MCU（漫威电影宇宙）等超级IP大片持续主导市场，导致小成本电影生存空间缩小。

4.2. 新闻联播效应

概念

• “新闻联播效应”（Xinwen Lianbo Effect）指的是 内容同质化现象，即 所有用户看到的内容高度相似，缺乏多样性。
• 这种效应通常发生在 内容分发平台、社交媒体、搜索引擎等信息流推荐场景，由于算法或政策限制，用户被推送类似的信息，导致视野受限。

原因

• 信息茧房（Filter Bubble）：推荐算法基于用户的历史行为，只推送用户“可能感兴趣”的内容，导致信息圈越来越封闭。
• 主流导向：官方或平台出于管理需求，可能会控制信息流，强调特定议题，削弱其他内容的曝光度。
• 算法收敛：推荐系统优化点击率，逐渐收敛到某些最受欢迎的内容，使得不同用户看到的内容趋于一致。

影响

• 用户多样化需求被忽视：用户接触到的信息局限于某一类型，减少了接触不同观点和内容的机会。
• 创新受限：内容创作者可能会趋同于热门话题，减少多样化创作。
• 社会认知固化：大众观点趋同，难以形成多元讨论，可能加剧偏见或误导公众认知。

典型案例

• 短视频平台的推荐机制：如果你刷短视频时喜欢看某类内容（如健身、美食），推荐算法会持续推送类似的视频，导致信息单一化。
• 微博热搜：某些新闻和话题反复出现，而其他可能同样重要的议题被忽视。
• 搜索引擎优化（SEO）：搜索引擎根据用户的历史记录调整结果排序，用户可能总是看到相似的信息，而忽略其他观点。

4.3. 主要区别

维度	哈利波特效应	新闻联播效应
核心现象	头部内容占据绝大部分流量，长尾内容难以崛起	所有人看到的信息趋于相似，内容同质化
主要影响	资源向头部集中，爆款效应加剧，内容多样性受影响	信息茧房效应加剧，用户认知受限，创新受阻
主要原因	马太效应、社交传播、平台推荐机制	信息茧房、主流导向、算法收敛
典型案例	哈利·波特、抖音爆款视频、漫威电影	短视频推荐、微博热搜、SEO个性化搜索

五、3. 无重复字符的最长子串（力扣hot100_滑动窗口）

• 思路1：
  维护一个tmp_s，遍历s，如果遇到重复字符，将tmp_s中重复字符及其之前的元素都删除。index= list.index(“s”) 就可以得到当前元素在列表中的第一个位置
• 代码：

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:tmp_s = []max_len = 0for i in s:if i not in tmp_s:tmp_s.append(i)max_len = max(max_len, len(tmp_s))else:max_len = max(max_len, len(tmp_s))index = tmp_s.index(i)               tmp_s = tmp_s[index+1:]tmp_s.append(i)return max_len

• 思路2：滑动窗口+哈希表
  维护一个哈希表，记录每个字符最后出现的索引。遍历s，tmp_s的左边界为max(i.index, 左边界)，右边界为当前字符i在s中的位置
• 代码：

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:dic = {}left = -1res = 0for right, s1 in enumerate(s):if s1 in dic:                     # 出现重复字符left = max(dic[s1], left)     # 计算当前重复字符上一个位置和字串的初始位置的最大dic[s1] = rightres = max(res, right-left)return res