airbnb招牌题DisplayPage实战分页结果去重又不乱序怎么做【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb本文带你拆解 airbnb 面试题仓库gh_mirrors/ai/airbnb中的招牌题 DisplayPage搜索结果分页展示时如何保证同一 host 在一页内最多出现一次同时又不打乱原始打分顺序。这是分页去重类面试题的经典模型读完你会掌握循环扫描 页内去重集合的完整解法。 题目分页去重的业务背景在 Airbnb 的真实搜索场景中结果是一条条 CSV 字符串按相关性分数排好序1,28,300.1,SanFrancisco 4,5,209.1,SanFrancisco 20,7,208.1,SanFrancisco 1,16,205.1,SanFrancisco - host 1 又出现了 ...每条数据的第一列是 hostId房东 ID。一个房东可能拥有多个房源如果按分数直接分页同一房东的房源可能霸占整页。题目的要求是每页固定展示 12 条结果同一 host 在一页内最多出现一次可能时尽可能保持原始分数顺序输出用空行 分隔的多个页块。题目完整描述见项目根目录的 README 第 4 题源码位于src/main/java/display_page/DisplayPage.java。 核心思路循环扫描跳过不删除很多人第一反应是把重复 host 的结果删掉但这会丢数据。正确姿势是跳过defer用指针从头扫描待显示列表同时用一个集合记录当前页已出现的 hostId当前项的 host 未出现过 → 放入结果页并从原列表移除它已经上岗已出现过 →原地跳过它留在列表里等待下一页轮到自己凑满一页 → 清空集合插入分页符从头再扫扫完一整圈仍没凑满剩余 host 数不足一页→ 开放行模式reachEnd剩余结果直接放行不再去重。一句话总结去重只发生在页内被跳过的项自然滚到下一页顺序因此天然保持。 源码解读两个版本的差异DisplayPage.java中提供了两个实现类对比阅读收益最大版本页内去重容器时间复杂度contains适用场景SolutionArrayList containsO(n)直观易懂适合白板讲解Solution_2HashSet counterO(1)面试推荐性能更优两个版本的关键逻辑几乎一致核心判断都是这一句位于Solution_2类中if (!set.contains(id) || reachEnd) { res.add(cur); // 收录进结果 set.add(id); // 标记本页已出现 iter.remove(); // 从待显示列表移除 counter; }三个易错点值得注意凑满一页后必须set.clear()并重置迭代器回到列表头否则下一页无法轮询被跳过的项分页符只在列表非空时插入避免最后一页尾部多一个空行测试断言里恰好验证了这一点扫完一圈回到头时要置reachEnd true否则剩余 host 不足一页时会死循环。✅ 用单元测试验证结果正确性DisplayPage.java文件末尾的UnitTest类内置了两个测试用例覆盖了核心场景用例 130 条结果、页大小 12 → 输出 32 项30 条结果 2 个分页符。断言了首页末位是11,26,107.1,Oakland、分页符位置、以及末页放行模式下的1,3,5.1,Oakland用例 213 条结果、页大小 5 → 输出 15 项。该用例里 host 6 有 4 个房源可以直观看到它被均匀摊到了不同页。运行测试项目要求 Java 11、Gradle 5.6# 拉取代码 git clone https://gitcode.com/gh_mirrors/ai/airbnb # 只跑 DisplayPage 这道题的测试 gradle -Dtest.singleDisplayPage test 面试拿分技巧小结先复述需求确认去重只限页内、允许跨页重复、顺序保持三条约束面试官最看重边界理解先讲思路再写码用跳过而非删除一句话讲清 defer 策略主动点出复杂度ArrayList 版 contains 是 O(n)换成 HashSet 降到 O(1)这是现成的加分优化点主动讨论边界host 数不足一页怎么办reachEnd 放行模式、分页符会不会多余——源码测试用例恰好覆盖能复述出来会非常加分。这道题的精髓在于把分页去重转化为带记忆的循环扫描记忆set随页清空列表随收录缩短两者配合就同时满足了不重复、不乱序、不丢数据三个要求。【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
`)
