Apple DS VO 面试真题解析:司机 8 小时滑动窗口最高收入与奖金计算
Apple 数据科学(DS)与数据工程(DE)的 VO 技术轮里,时间序列的滑动窗口几乎是必考题。这道“司机连续 8 小时最高收入”表面上看只是分组求和,真正动起手来,面试官会盯着你的窗口边界开闭、SQL 自连接的性能瓶颈,以及 Python 双指针的复杂度一路往下抠。
这篇复盘围绕 Apple DS VO 的实战训练素材。Apple 不同业务线(如 Maps、Services、Apple Pay 等)对 DS 候选人的代码考察侧重不同:有的组要求直接手写纯 SQL,有的组更喜欢让你用 Python(原生数据结构或 Pandas)现场跑通测试样例。因此我们在复盘时把 SQL 和 Python 两套标准解法都准备齐了,具体流程请以你收到的面试通知为准。
题目描述
给定一张行程记录表 Trip(包含字段 trip_id、driver_id、start_time、earnings),请找出每位司机在任意连续 8 小时时间窗口内的最高总收入(Highest Total Trip Earnings)。
- 窗口定义:以任意一笔订单的
start_time作为窗口起点t,将该司机在随后 8 小时内开始的所有订单纳入同一个窗口。 - 输出要求:按每位司机的最大 8 小时累计收入从高到低排名,并按该峰值收入的 10% 计算激励奖金(Bonus)。
核心思路与破题关键
拿到这类“任意连续 N 小时最大值”的题目,千万不要按自然日的固定班次(比如 0:00–8:00、8:00–16:00)去切分。题干已经说得很透:每个有效窗口都锚定在某笔真实订单的 start_time 上。也就是说,如果一个司机全天跑了 m 单,最多只需要评估以这 m 个时间点为起点的窗口即可,跨夜订单(比如晚上 22:00 到次日早上 6:00)也天然包含在内。
动手写代码前,先跟面试官快速对齐两个口径:
- 右边界闭区间还是开区间?假设第一单是
08:00:00,那么16:00:00整点开始的订单算不算在同一个 8 小时窗口里?口述确认是闭区间[t, t + 8h]还是左闭右开[t, t + 8h),下面代码默认按闭区间[t, t + 8h]处理。 - 并列排名怎么算?两个司机最高收入一模一样时,用
DENSE_RANK还是RANK?通常算奖金排行榜首选DENSE_RANK。
解法一:SQL 实现(RANGE 窗口函数 vs 自连接)
在 SQL 轮里,很多候选人第一反应是写 Trip t1 JOIN Trip t2 ON t1.driver_id = t2.driver_id AND t2.start_time BETWEEN t1.start_time AND t1.start_time + INTERVAL '8 hours'。自连接虽然逻辑直观,但在大表下会产生接近 O(m²) 的中间膨胀行。更地道的写法是直接用支持时间偏移的 RANGE 窗口函数(PostgreSQL、Spark SQL、BigQuery 均原生支持):
WITH window_earnings AS (
SELECT
driver_id,
start_time,
SUM(earnings) OVER (
PARTITION BY driver_id
ORDER BY start_time
RANGE BETWEEN CURRENT ROW AND INTERVAL '8 hours' FOLLOWING
) AS earnings_8h
FROM Trip
),
driver_peak AS (
SELECT
driver_id,
MAX(earnings_8h) AS max_8h_earnings
FROM window_earnings
GROUP BY driver_id
)
SELECT
driver_id,
max_8h_earnings,
ROUND(max_8h_earnings * 0.10, 2) AS bonus,
DENSE_RANK() OVER (ORDER BY max_8h_earnings DESC) AS earnings_rank
FROM driver_peak
ORDER BY earnings_rank, driver_id;
写完这段 SQL 可以主动向面试官补充一句:这里故意用 RANGE 而不是 ROWS,一是因为司机在 8 小时内接单数量不固定,二是当同一个司机在同一秒有两条合并入账记录时,RANGE 会自动把同时间戳的记录归入同一个边界内,不会漏算。
解法二:Python 实现(分组排序 + 双指针滑动窗口)
如果面试官让你切到 Python 环境写算法函数,千万别在每个起点往后套一层内循环去暴力累加(最坏 O(m²))。对每个司机的订单按 start_time 排好序后,因为时间戳单调不减,窗口的左右端点 left 和 right 只会向右推进、绝不回退——直接用双指针(Sliding Window)就能把组内扫描压到严格的线性时间 O(m)。
from collections import defaultdict
from datetime import timedelta
def rank_drivers_by_8h_peak(trips):
"""
trips: list of dicts, e.g.
[{'driver_id': 101, 'start_time': datetime(...), 'earnings': 25.0}, ...]
"""
by_driver = defaultdict(list)
for t in trips:
if t.get('earnings', 0) is not None:
by_driver[t['driver_id']].append((t['start_time'], float(t['earnings'])))
peak_records = []
window_span = timedelta(hours=8)
for driver_id, records in by_driver.items():
records.sort(key=lambda x: x[0])
n = len(records)
left = 0
curr_sum = 0.0
max_sum = 0.0
for right in range(n):
curr_sum += records[right][1]
# 收缩左边界,保证窗口跨度不超过 8 小时(闭区间 [t, t + 8h])
while records[right][0] - records[left][0] > window_span:
curr_sum -= records[left][1]
left += 1
if curr_sum > max_sum:
max_sum = curr_sum
peak_records.append({
'driver_id': driver_id,
'max_8h_earnings': round(max_sum, 2),
'bonus': round(max_sum * 0.10, 2)
})
# 按峰值收入降序排列,并计算 Dense Rank
peak_records.sort(key=lambda x: (-x['max_8h_earnings'], x['driver_id']))
rank = 0
prev_earnings = None
for item in peak_records:
if item['max_8h_earnings'] != prev_earnings:
rank += 1
prev_earnings = item['max_8h_earnings']
item['rank'] = rank
return peak_records
时间复杂度主要花在分组后的组内排序上,设总订单数为 N,整体时间复杂度为 O(N log N),双指针滑动本身只有 O(N) 的加减操作;空间复杂度为 O(N)。
面试官常见追问(Follow-ups)
追问一:如果存在退款、取消单或负数收入,双指针还能用吗?
这是 DS 算法轮非常经典的挖坑点。如果表里都是正数收入,窗口越长总和越大,所以右指针每推进一步、左指针收缩完之后,当前极值一定代表以 left 附近为起点的最优窗口。但如果表里混入了负数(比如乘客投诉扣款、平台罚款调整),窗口变短反而可能让总和变大。此时单纯靠 while 被动收缩左边界会漏掉“提前收缩左边界以甩掉负收益订单”的更优子窗口。
应对方案:先在业务层向面试官确认异常单(取消单、退款单)是不是应该在进入窗口统计前通过 WHERE status = 'completed' AND earnings > 0 过滤掉;如果业务上必须保留负数冲抵,那就得用前缀和配合单调队列(Monotonic Queue)来维护窗口内的最小前缀和。
追问二:同一笔订单长途跨了 10 小时,怎么防止刷单作弊?
题干只按 start_time 判断订单是否落入 8 小时窗口。如果某个司机在 08:00 接了一单小活,然后在 15:59(第 8 个小时的末尾)接了一单耗时 5 小时的高价跨城长途单,按现有规则,这两单的收入会全额算进同一个 8 小时窗口里,尽管实际服务时长已经接近 13 个小时。
在讨论业务落地时可以主动指出这个漏洞:如果奖金核算要求“实际工作时长在 8 小时内”,窗口过滤条件就要改成同时卡住首尾——不仅要求 t2.start_time >= t1.start_time,还要加上 t2.end_time <= t1.start_time + INTERVAL '8 hours',或者对跨出窗口边界的订单按时间比例(Pro-rata)折算收入。
追问三:如果用 Pandas 一行代码怎么写?
如果面试官问起 Pandas 的向量化实现,可以直接答:先把 start_time 设为索引并按司机分组排序,然后用 df.groupby('driver_id').rolling('8h', on='start_time')['earnings'].sum()。但要注意提醒面试官,Pandas 默认的 rolling('8h') 是向过去回看 8 小时(即 [t - 8h, t])。由于对于任意一段连续 8 小时区间,无论从左端点往右看 8 小时,还是从右端点往左回看 8 小时,拿到的最大区间和在数学上是完全等价的,所以在只求 max() 峰值时可以直接用!
备考与实战建议
准备 Apple DS 的技术面,千万不要把 SQL 和 Python 割裂开练。很多时候面试官先让你写完 SQL,紧接着就会问“如果这段逻辑挪到离线 Python 脚本里跑,你怎么测边界?复杂度是多少?”。平时刷题时养成习惯:看到时间窗口题,先问清区间开闭、时区对齐(UTC 还是司机本地时区)、异常负值过滤以及并列排名规则,这四个问题一抛出来,你的工程成熟度立刻就能和普通背题党拉开差距。
FAQ
SQL 里算 8 小时滑动窗口,为什么一定要用 RANGE 而不是 ROWS?
因为司机接单是不定时的,8 小时内可能跑了 2 单,也可能跑了 15 单。ROWS 按物理行数截取,没法处理不固定条数的时间跨度;RANGE 才能直接按时间戳偏移量(如 INTERVAL '8 hours')框定真实物理时间窗口。
窗口边界是按 start_time 还是 end_time 算?包含右端点吗?
题干明确约定窗口从某单的 start_time 开启,统计接下来 8 小时内“开始”的行程,因此统一看 start_time。但是否包含恰好在 t + 8 hours 整点开始的订单(即闭区间 [t, t+8h] 还是左闭右开 [t, t+8h)),写代码前必须跟面试官确认。
多位司机最高 8 小时收入并列时,排名函数怎么选?
涉及到发奖金或激励排行榜时,通常用 DENSE_RANK() 让并列司机拿到相同名次且不跳号,或者用 RANK() 留出并列空位;如果不允许名次并列,则需要让面试官补充二级排序字段(比如总完单量或最早达成该峰值的时间)。
参考来源
- PostgreSQL 官方文档 — Window Functions (RANGE & INTERVAL Framing)
- Pandas 官方文档 — DataFrame.rolling 时间序列滚动窗口
- LeetCode 题单 — Sliding Window 滑动窗口与双指针专题
联系 VOPathway
如果你正在准备 Apple 或其他北美科技大厂的 DS / DE / SDE 面试,想针对性打磨 SQL 高阶窗口函数、Python 数据处理或业务 Case 追问,欢迎把目标岗位和面试时间发给 VOPathway,我们提供定制化的 1v1 实战演练与复盘。
- 微信:Coding0201
- 邮箱:catcstech@gmail.com
- Telegram:@OAVOProxy
- WhatsApp:+86 178 6396 8105
可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考,不代表相关公司的官方流程;实际安排请以候选人收到的通知为准。
本文用于面试准备与训练复盘。公司名称仅用于标识题型素材主题,不代表官方合作或录用承诺。
预约一次训练复盘 ↗