Applied Research / MLE · 70 分钟 OA

Capital One 仓库轮转派送:容量重置、禁用与同分最大索引

Applied Research OA 的仓库/服务器派送题:跳过禁用和满载实体,全部不可用时重置容量,统计接单数并处理无可用仓库。

题目重点:Applied Research OA 的仓库/服务器派送题:跳过禁用和满载实体,全部不可用时重置容量,统计接单数并处理无可用仓库。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 主训练版每次配送从 0 搜索,按 0→n−1 顺序找未禁用且剩余容量>0; 的接续指针作为变体单独说明。
  • 每次成功配送消耗 1 容量、累计仓库处理数+1;禁用是永久禁用,容量重置不重新启用。
  • 若无仓库可用但至少有一个启用且初始容量>0,则重置所有启用仓库的剩余容量再重试一次;若所有均禁用/初始容量 0,返回无可派送状态而非死循环。
  • 最高数同分返回最大索引;如果一件都未派,返回值依接口确认,训练版可返回 -1。

解题路线

  1. 明确 `delivery` 与 `disable(index)` 操作格式、搜索起点是否接续、重置是否恢复禁用、处理不了包裹时是报错还是跳过。
  2. 初始化 remaining=capacity、disabled=false、handled=0;处理禁用只更新标志,不改历史 handled。
  3. 配送时按约定起点环扫最多 n 次,找到可用者扣容量并加 handled;找不到就检查是否存在启用且初始容量正的仓库,再重置可用实体容量并最多重试一次。
  4. 结束用 (-handled,-index) 取最大,或扫描中 `handled[i]>bestCount 或 == 且 i>bestIndex`;不要按剩余容量评选。
  5. 若输入量很大,可维护可用索引有序集合与轮转 epoch;但重置、禁用会改变集合,先以简单模拟对照验证。

手动走一遍

训练 capacity=[1,2],三次配送从 0 搜索:第 1 次给 0、第 2/3 次给 1,handled=[1,2],返回 1。再禁用 1,后续 0 满时重置 0 的容量后派给 0,disabled 的 1 不复活。若两者都禁用,再来配送必须停止。接续游标变体的前几次分配可不同。

规模与取舍

n 个仓库、d 条日志的朴素实现每次派送最多两圈 O(n),总 O(dn) 时间、O(n) 状态空间;维护可用集合可将常规查找降至 O(log n),重置需按仓库数处理或用 epoch 惰性策略。

易错点与追问

容易失分的边界

  • 所有仓库永久禁用时反复 reset 导致无限循环。
  • reset 把 disabled 也清除。
  • 按剩余容量或处理次数最少分配,违背轮转规则。
  • 同分返回最小索引。
  • 把每次从 0 与接续指针两个帖的描述混为固定原题。

继续深挖

  • 每次从上次位置继续时如何维护指针?
  • 重置是否只在容量全部耗尽时发生?
  • 禁用仓库已处理的数量是否仍计最终排名?
  • 百万仓库/日志时怎样用有序集合或批量跳过?
✓已复制微信号!