SWE · OA

TikTok 电池回充模拟:耗尽事件、可用时间与缺失政策

复现16分钟样例的7次耗尽,解释最后一块未耗尽不计数,并列出必须澄清的规则。

题目重点:复现16分钟样例的7次耗尽,解释最后一块未耗尽不计数,并列出必须澄清的规则。

题意与假设

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

  • 已给capacity=[2,2,1,5]、recharge=[1,4,3,5]、使用16分钟例子。
  • 未给下一块未充好时等待、跳过还是失败,不能推出所有输入的唯一返回值;正文分析已知例子和政策分支。

解题路线

  1. 每块维护readyAt时间,开始全部可用。一次耗尽结束时t增加capacity,readyAt=t+recharge,耗尽次数加1;最后使用时长小于capacity则不耗尽、不加计数。
  2. 例子依次用1/2/3/4/1/2/3,共2+2+1+5+2+2+1=15分钟,7块耗尽;剩1分钟用第4块,未耗尽所以返回7。
  3. 使用不必按分钟更新每块负数,比较绝对readyAt可直接跳到事件;若恰用完整capacity到目标终点,是否算耗尽需约定,通常按已完整用完计入。
  4. 下一候选readyAt>t时有三种不同合同:等待会增加墙钟时间,跳过会改轮转次序,失败会结束。应先澄清“用16分钟”是连续服务还是累计开机时长,不能随意补一条。
  5. 满充后是否保持capacity、回充何时开始和可否中途切换也影响模拟;明确这些后再写通用实现和对照测试。

手动走一遍

第4块t=10耗尽,readyAt=15;下一轮前三块在t=12/14/15依次耗尽,t=15第4块已经充好,用1分钟结束。若只有一块capacity2/recharge10,连续运行3分钟会遇到政策缺口,样例不能告诉你是等、失败还是允许中断。

规模与取舍

已知政策下每次耗尽一事件,E次耗尽、n块空间O(n);找可用候选可O(nE)朴素或按政策设计事件结构,不承诺缺规则时统一复杂度。

易错点与追问

容易失分的边界

  • 把使用过但未耗尽也计数。
  • 按样例擅自决定等待/跳过。
  • 混同墙钟时间和累计开机时间。

继续深挖

  • 没有可用电池怎样处理?
  • 终点恰好耗尽是否计数?
  • 如何对照逐分钟模拟?
✓已复制微信号!