找出 1 亿行 URL 中域名不在 1 万域名表中的行
哪些公司问过
答案要点
- b 仅 1 万条,放入内存哈希集合;a 流式逐行处理,无需全部加载
- 从 URL 解析主机名,处理协议、端口、用户信息,统一转小写等规范化
- 每行 O(1) 查找,整体 O(n),瓶颈在 IO,可按行对齐分段并行
- 确认子域名是否算匹配,算则逐级取后缀查集合
- 不宜用布隆过滤器,其误判会导致应输出的行被漏掉
易错点
- 用简单字符串截取解析 URL,遇到端口或用户信息时出错
- 不确认子域名匹配规则就动手
- 用布隆过滤器判断不存在之外的场景,忽略误判方向
面试官常见追问
- 如果 b 也很大,内存放不下怎么办?
- 解析 URL 时有哪些容易出错的地方?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。