算力手记C++ & COMPUTING SYSTEMS
← 12套面试训练

LOOP 08 / INTERVIEW LOOP / 4H

Scan 与稳定筛选：从标记推导输出位置

一个输入序列要只保留正数，且顺序不能改变。面试官把“每个线程找到空位”作为诱导，你要先通过 scan 给每个保留项一个确定的位置。

完成单元 57 · 用 shape 与 stride 接上矩阵计算及其先备后安排本次训练。不绑定日历周。

先写自己的答案，再展开参考。这里按技能编写问题，不声称公司真题；自评与阅读都不会自动通过 G0。

先备与学习位置

回到对应的路线里程碑 →

TIME WITH OUTPUTS

240 分钟怎样用

  1. 闭卷恢复先备 · 15min

    闭卷区分 inclusive/exclusive scan、total、稳定性；说明 host/device 之间复制和完成等待的生命周期前提。

    留下：先不查章节，写三条判断和一个不确定点；再只补读相关章节的解释段。

  2. 澄清题目与手算 · 25min

    读主问题，逐条写输入、输出、范围与失败行为。手算前两个公开用例，给自己的方案找一个反例。

    留下：一份接口合同、逐步状态表和最小反例；不要先打开参考推演。

  3. 独立实现或设计 · 55min

    先实现一个串行 C++ oracle：输入 vector<int>，为正数生成 1、其余生成 0 的 flags；计算 exclusive prefix；将正数写到 prefix 给出的输出下标。提交 flags、prefix、count、output 四项，然后给出逻辑并行划分。不要把本机 oracle 称为 GPU kernel。

    留下：保存个人代码或设计稿。编码题保留编译命令；设计题为每个事件编号，不能只画没有状态的箭头。

  4. 边界与反证 · 25min

    用题目的全部公开用例核对真实输出；另外创造一个与公开输入不同的边界。发现失败时缩小输入，再解释修复。

    留下：实际结果、原始失败和修复原因各一份；设计题记录一个被拒绝的执行顺序。

  5. 按表现进入追问树 · 35min

    从 n1 开始。每题先录下自己的回答，再展开标准；按满足或未满足条件跳转。树最多走一轮，卡住时把剩余时间用于分支中的纠错，不循环加时。

    留下：记录经过的节点、原话、缺失条件和修订；只会复述标准的节点仍标记待重做。

  6. 英文口述与打断 · 30min

    用本页英文提纲录制两轮 90 秒回答；第二轮在 30 秒处自问追问，先回答追问再回到主线。每轮回听并改写两个含糊句。

    留下：两轮录音或逐字稿；圈出输入、因果、边界和限制各一句。参考英文在录完第一轮后再读。

  7. 复盘与安排重做 · 25min

    对照强弱答案，选择一个真正出错的环节：合同、状态、实现、验证或表达。填本页记录模板，并约定下一天的 30 分钟。

    留下：一个有失败输入的错误记录和一个可观察修复标准；不要把全部问题归因为粗心。

  8. 次日无答案重做 · 30min

    次日改保留条件为 x≥0，对 [-1,0,2,0,-3] 独立生成四项结果。然后纸上按前两项与后三项分块，算局部计数与块偏移。

    留下：这是本周 240 分钟中的最后 30 分钟，不另加预算。先关闭解答，用 20 分钟独立做，再用 10 分钟核验并记录是否仍需复习。

包括次日重做，总计 240min。局部错因复盘属于本次练习，额外的计划复盘按实际需要另记。

SOLVE BEFORE READING THE ANSWER

先独立处理这个问题

先实现一个串行 C++ oracle：输入 vector<int>，为正数生成 1、其余生成 0 的 flags；计算 exclusive prefix；将正数写到 prefix 给出的输出下标。提交 flags、prefix、count、output 四项，然后给出逻辑并行划分。不要把本机 oracle 称为 GPU kernel。

输入与输出合同

  • 输入最多 100 项、值在 [-100,100]；保留条件严格为 x>0。
  • exclusive prefix[i] 表示 i 之前保留项的数量，不包括当前项。
  • 总 count 等于 flags 之和；输出长度精确为 count，保持原相对次序。空输入全部为空、count=0。
手算之后，对照公开用例
输入或情形预期为什么
a=[0,5,-1,5,2]flags=[0,1,0,1,1]; prefix=[0,0,1,1,2]; count=3; output=[5,5,2]两个 5 都保留，0 不保留。
a=[]flags=[]; prefix=[]; count=0; output=[]不能读最后一个前缀。
a=[-2,0]flags=[0,0]; prefix=[0,0]; count=0; output=[]没有有效输出位置。
a=[3]flags=[1]; prefix=[0]; count=1; output=[3]第一项的 exclusive 位置为 0。

先保留自己的解法、状态轨迹与验证记录，再打开参考。允许用自然语言或伪代码补充解释；不能用参考输出代替真实运行。

保存独立尝试后，阅读解法与状态轨迹

解法依据

遍历输入生成 flags；设置 running=0，对每个 i 先把 running 写入 prefix[i]，再加 flags[i]。循环结束的 running 就是 count，不需要从最后一项推导，因而自然处理空输入。分配 count 项结果；仅对 flag=1 的位置写 output[prefix[i]]=input[i]。保留项的前缀严格递增，因此写入位置互不冲突，且按输入顺序排列。

逐步推演

[0,5,-1,5,2] 的 running 在各次写前缀时为 0,0,1,1,2；最后为 3。保留项索引 1、3、4 分别写 0、1、2。若误用 inclusive prefix，会得到 1、2、3，从 1 开始且最后越过长度为 3 的输出。

FOLLOW THE ANSWER, NOT A SCRIPT

从回答进入下一层追问

从 n1 开始。先录下回答，再展开判定；达到条件就走深入分支，未达到就按反馈缩小问题。一次最多走一轮，不靠反复查看同一答案累积“通过”。

把实际走过的节点记入模板 →

NODE n1

把 exclusive 改成 inclusive 后，单元素 [3] 会写到哪里？

我已作答：查看判定与下一分支

需要解释清楚：写到 1，而长度只有 1，合法下标仅 0；必须用前面元素数量作为位置。

达到

结论正确，并解释本节点给出的具体状态或反例。

保留关键推理：写到 1，而长度只有 1，合法下标仅 0；必须用前面元素数量作为位置。

继续到 n2 →

待补

只报术语、漏掉条件，或不能解释题中的数值。

分别列“此前数量”和“包含自己数量”，用 [3] 画唯一输出格。

继续到 r1 →

NODE r1

把第一个追问缩到最小输入，重新逐步说明。

我已作答：查看判定与下一分支

需要解释清楚：写到 1，而长度只有 1，合法下标仅 0；必须用前面元素数量作为位置。

修复后达到

用具体输入改正原回答，能指出之前错在哪里。

分别列“此前数量”和“包含自己数量”，用 [3] 画唯一输出格。

继续到 n2 →

仍未达到

仍依赖答案复述，不能独立重建状态。

本次树到此结束；把 n1 的输入和缺口写入复盘，再进入英文练习与次日重做。

这一分支结束：对照并复盘 →

NODE n2

零保留项时能直接访问 prefix.back() 吗？

我已作答：查看判定与下一分支

需要解释清楚：空输入不能访问；用累计总数天然处理空和全不保留。即使非空也需要正确结合最后 flag，不能混淆 prefix 与总数。

达到

结论正确，并解释本节点给出的具体状态或反例。

保留关键推理：空输入不能访问；用累计总数天然处理空和全不保留。即使非空也需要正确结合最后 flag，不能混淆 prefix 与总数。

继续到 n3 →

待补

只报术语、漏掉条件，或不能解释题中的数值。

分别手推 [] 和 [-2,0]，让计数通过循环得到。

继续到 n3 →

NODE n3

两个 block 各自 scan 完，就能直接拼成全局位置吗？

我已作答：查看判定与下一分支

需要解释清楚：必须为后续 block 加前面 block 的保留总数；block 内同步不能完成跨 block 前缀依赖。

达到

结论正确，并解释本节点给出的具体状态或反例。

保留关键推理：必须为后续 block 加前面 block 的保留总数；block 内同步不能完成跨 block 前缀依赖。

这一分支结束：对照并复盘 →

待补

只报术语、漏掉条件，或不能解释题中的数值。

用 flags=[1,0 | 1,1]：局部位置后块从 0 起，需加前块总数 1 才不冲突。

这一分支结束：对照并复盘 →

答案强在哪里，弱在哪里

保存自己的回答后，打开对照

弱答案

“每个线程 atomic++ 拿一个位置，输出顺序应该差不多。”

强答案

“题目要求稳定顺序，因此位置必须由输入之前的保留数量决定。exclusive scan 给出位置，正数项映射到 0 到 count-1。原子计数可以分配互斥位置，但执行先后通常不保证原输入次序。”

强答案区分唯一位置和稳定顺序两个要求，并通过前缀的严格递增解释无冲突。它没有将数学索引正确性当作设备同步或性能的证明。

在自己的原回答里划出一个缺失的条件或错误推理，再重说一遍。完整句子背熟，不代表能处理新约束。

ANSWER, THEN HANDLE AN INTERRUPTION

英文口述与打断

Explain the difference between unique output slots and stable order.

  1. Define the exclusive prefix.
  2. Trace the two retained fives.
  3. State what the CPU oracle does not prove.

“Would an atomic counter give the same ordering?”

录完第一轮后，读英文示范
The exclusive prefix counts retained elements before the current position. It gives every retained element a unique slot while preserving input order. In the example, the two fives occupy slots zero and one, so neither is deduplicated. The CPU oracle checks the mathematical mapping; it does not verify device synchronization or GPU performance.
  • 前 15 秒说明输入、输出和一个关键约定。
  • 至少用一个本题的数值解释因果，不只罗列英文术语。
  • 明确一个边界或尚未验证的限制；不能把教学推演说成项目经验。

次日关掉解答，换一个问题

次日改保留条件为 x≥0，对 [-1,0,2,0,-3] 独立生成四项结果。然后纸上按前两项与后三项分块，算局部计数与块偏移。

独立重做后核对

flags=[0,1,1,1,0]；prefix=[0,0,1,2,3]；count=3；output=[0,2,0]。块总数=[1,2]，块偏移=[0,1]；后一块保留项位置需要加 1。

  • 关闭主问题答案并使用新输入独立完成。
  • 给出结果与原因；失败时记录最小反例，不能只把完成标记改成通过。

重做的 30min 已计入本套4h；需要更多补课时记录实际用时，按缺口顺延。

记录实际回答与证据

本次面试练习模板
# W08 算法 / 英文训练记录（仅个人练习，不是能力认证）
日期：
本次先备与尚不确定点：
主问题接口合同：
我最初的方案与状态表：
运行命令或设计事件编号：
失败输入 / 预期 / 实际：
修复与理由：
追问路径（节点 → 自己原话 → 缺口）：
英文第一轮两处含糊句：
英文第二轮修订：
次日重做日期（30 分钟已含本周预算）：
重做输入 / 实际结果 / 解释：
仍需补练：

本次练习的检查依据

四项结果及空输入正确；能从 prefix 证明写入位置唯一与稳定；明确跨块偏移和实际设备验证未完成。

模板在你的个人笔记中填写。网页只提供空模板；不会把这次训练写成项目经验或学习验收结果。