Waymo 电话面试面经

想要了解更多面试代面服务，扫码添加微信，获取更多信息：

面试题目

在此次电话面试中，面试官要求编写一个程序，用于计算不同路段上车辆的平均速度。这类似于简化版的 Google 地图交通指示器。道路被抽象为一条从 0 开始并向上延伸的线段。

题目描述

目标：
- 计算道路上不同位置的车辆平均速度。

输入指令：
1. `add A B S`：添加一辆车的速度数据，起始位置为 A，结束位置为 B，速度为 S。
2. `delete A B S`：删除一条速度数据。
3. `query A`：查询位置 A 的平均速度。
4. `end`：表示输入结束。

注意：
- 位置以整数表示，速度为整数。
- 区间是左闭右开 `[A, B)`，包含起始位置，不包含结束位置。
- 当查询位置没有任何车辆数据时，输出 0。

示例输入：
add 5 10 20
add 7 15 30
query 6      // 输出: 20
query 8      // 输出: 25
query 25     // 输出: 0
add 20 30 15
query 25     // 输出: 15
delete 5 10 20
query 6      // 输出: 0
end

示例输出

20
25
0
15
0

示例解释

• 在位置 6，只有一辆车的速度为 20 mph，所以平均速度为 20。
• 在位置 8，有两辆车，速度分别为 20 mph 和 30 mph，平均速度为 (20 + 30) / 2 = 25。
• 在位置 25，没有车辆数据，输出 0。
• 添加了区间 [20, 30) 的车辆速度 15 mph 后，查询位置 25，平均速度为 15。
• 删除了区间 [5, 10) 的速度数据后，查询位置 6，没有车辆数据，输出 0。

解题思路

为了高效地处理添加、删除和查询操作，需要使用能够快速检索区间并计算平均速度的数据结构。区间树（Interval Tree） 是一种适合解决此类问题的数据结构。

数据结构设计

定义一个区间树节点 IntervalTreeNode，包含以下属性：

• low：区间的起始位置。
• high：区间的结束位置。
• speed：该区间的速度。
• max：当前节点子树中的最大结束位置。
• left：左子树。
• right：右子树。

核心函数

插入函数 insert

def insert(root, node):
    # 将新节点插入区间树，维护区间树的性质和 max 值

删除函数 delete

def delete(root, low, high, speed):
    # 在区间树中找到匹配的节点并删除，更新 max 值

查询函数 query

def query(root, point, result):
    # 查询包含指定点的所有区间，收集速度数据

主函数

def main():
    root = None
    while True:
        line = input().strip()
        if line == 'end':
            break
        parts = line.split()
        # 处理不同的指令：add、delete、query

测试结果

根据示例输入，程序应输出：

20
25
0
15
0

验证程序的正确性。

总结

这道题考察了对区间操作的数据结构设计和实现能力，特别是区间树的应用。通过使用区间树，可以高效地完成添加、删除和查询操作，满足题目的性能要求。