Original Question (English)
Given a list of movies from multiple providers pre-sorted based on rating, produce a list of movies that are sorted across all providers.
Example:p1 = {0, 3, 4}, p2 = {0, 2, 3}, p3 = {1}, p4 = {0, 2}
题目简述（口语化）
有多个内容提供方（providers），每个 provider 给了一份按评分已排序的电影列表。请把它们合并成一个全局有序的列表。
示例：p1 = [0,3,4], p2 = [0,2,3], p3 = [1], p4 = [0,2]
注：数字可理解为“评分”或“按评分排好序的电影ID的相对顺序”。是否去重、排序方向（升/降）需向面试官确认。
一、和面试官快速澄清（Clarifying Questions）
- 排序方向：升序还是降序？（默认升序）
- 是否去重：同一部电影在多个 provider 出现时，最终列表是否只保留一次？如何判定“同一部电影”（按ID还是按评分值）？
- 相同评分的 tie-breaker：同分时是否按 provider 顺序、原列表位置，或电影ID次序稳定排序？
- 数据规模：
k（providers数量）和总元素数m有多大？是否有内存/流式限制？ - 输出要求：仅返回合并后的列表，还是需要附带来源（providerId, index）等信息？
二、思路总览
解法 A：直接拼接后排序（Baseline）
- 做法：把所有列表拼起来，
sort()一下；如需去重，再线性扫一遍去重。 - 复杂度：时间
O(m log m)，空间O(m)。 - 优点：实现最快。
- 缺点：当
k大、每个列表已排序时，没有利用“各列表已排好序”的信息，性能不是最优。
解法 B：K 路归并（K-way merge with Heap）✅推荐
- 核心思想：用一个 min-heap（优先队列） 维护 “每个列表当前头部元素”。每次弹出全局最小的元素，并把该元素来自的那个列表的下一个元素压回堆。
- 数据结构：堆中元素形如
(value, providerId, indexInProvider)；需要自定义比较器处理 tie-breaker。 - 步骤：
- 把每个 provider 的第 1 个元素入堆；
- 循环：弹出最小值 → 追加到结果；如果该元素所在列表还有下一个，就入堆；
- 若去重：维护
seen（按电影ID或值），已见过则跳过。
- 复杂度：
- 时间：
O(m log k)（每个元素最多入堆/出堆一次，堆大小 ≤ k） - 空间：
O(k)（堆）＋O(u)（若去重需要的哈希；u为唯一元素数）
- 时间：
示例不去重的合并结果：
[0,0,0,1,2,2,3,3,4]
若按“电影ID去重”，可能得到：[0,1,2,3,4]（具体以澄清为准）
三、手撕思路要点（可直接口述/写伪代码）
function mergeKSorted(lists, dedup=false):
heap = new MinHeap( by: (value, providerId, idx) with tie-breaker )
for each provider i:
if lists[i] not empty:
heap.push( (lists[i][0], i, 0) )
result = []
seen = HashSet() // 仅在 dedup=true 时启用
while heap not empty:
(val, pid, idx) = heap.pop()
if !dedup or val not in seen:
result.append(val)
if dedup: seen.add(val)
if idx+1 < len(lists[pid]):
heap.push( (lists[pid][idx+1], pid, idx+1) )
return result
四、复杂度与正确性陈述
- 时间复杂度：
O(m log k) - 空间复杂度：
O(k)（堆）+O(u)（去重集合） - 正确性不变式：堆中始终保存每个列表的当前最小候选，弹出即全局最小。
五、常见追问与扩展
- Top-N：取前 N 次弹出即可，复杂度
O(N log k) - 降序：使用 max-heap 或比较器取反
- 流式数据：用迭代器封装每个 provider
- 去重维度：按 movieId 而非评分值去重
- 外部排序：大数据场景下的多阶段归并
六、csoahelp 实时辅助还原
以下为我们在实时辅导客户面试时的真实复盘：
- 读题阶段：提醒先问清排序方向、去重规则、tie-breaker
- 方案选择：建议先提 O(m log m) 再引出 O(m log k) 的堆优化
- 细节落地：我们实时提供
(val, providerId, idx)三元组结构，帮助候选人顺畅口述 - 示例推演：现场引导走一遍
[0,3,4], [0,2,3], [1], [0,2]，验证堆弹出顺序 - 收尾补充：提醒复杂度总结与扩展场景应对（Top-N、去重、流式）
在这种 K-way Merge 类型的面试题里，很多候选人其实卡的不是算法，而是在面试表达、思路组织和现场应变。
csoahelp 的实时辅助，可以让候选人在 30~45 分钟的面试里表现得更稳定、更有条理。
我们具体做的事：
- 第一分钟快速定位考点
- 你读完题，我们会马上帮你提炼核心考点（K-way merge、heap、复杂度优化等），让你有个明确的主线。
- 同时提示你优先问哪些澄清问题，确保不漏掉 tie-breaker、去重等容易失分的点。
- 思路组织 + 表达优化
- 现场给你一个可口述的伪代码结构，不用陷入“想写代码却卡半天”的尴尬。
- 帮你在讲解时自然过渡，例如从 O(m log m) 过渡到 O(m log k) 时，如何用“利用已排序信息”这种关键词打动面试官。
- 示例推演 + 正确性证明
- 在你答题过程中，我们同步推一遍例子，帮你发现潜在 bug（比如 tie-breaker 失效、去重逻辑错误）。
- 给你一套简短的正确性陈述，让你在回答中显得更严谨。
- 应对追问
- 面试官一旦问 “Top-N 怎么做”“降序怎么办”“流式数据如何处理”，我们会即时给你简洁且高分的答案模板。
- 避免你在变体问题上慌乱或答不全。
- 时间控制
- 帮你在规定时间内完成澄清 → 思路 → 代码/伪代码 → 测试 → 复杂度总结，不至于卡在某个环节。
效果：你不仅能写出正确的解法，还能在表达上条理清晰、应答流畅，让面试官对你整体技术素养和沟通能力都有好印象。
📩 如果你马上有一场面试，不想冒险 —— 来找我们。
不管你面对 google、Amazon、Meta 还是 TikTok，我们都能在面试过程中实时支持，确保你顺利答完题、讲清楚、留下好印象。
一场面试可能决定你能不能留下。我们会帮你，写好每一行代码，稳住每一个环节。
