Bloomberg 面试题：Bus Tracker 公交站点追踪器

题目描述

你正在开发一个公交追踪网站，用户可以查询公交车当前位置以及最近公交距离某站还有几站。公交车只在站点停靠，且只沿单向行驶。

class BusTracker {
  // stationList 是用连字符连接的站点列表
  // 如 "1-2-3-4-5" 表示 1 -> 2 -> 3 -> 4 -> 5
  // busLocations 是每辆车当前所在的站点
  constructor(stationList, busLocations) {}
  
  // 返回距离指定站点最近的公交还有几站
  // 公交只能往右走，如果所有车都在目标站左边则返回 -1
  nearestBusToStation(stationId: string): number { return -1; }
  
  // 返回指定公交当前所在站点
  getBusLocation(busId: number): string { return ""; }
}

示例

站点图：A-B-C-D-E-F-G-H-I
公交位置：{1: "B", 2: "E"}

busTracker.nearestBusToStation("A") // -1（没有公交在A或A右边）
busTracker.nearestBusToStation("B") // 0（1号车就在B站）
busTracker.nearestBusToStation("C") // 1（1号车在B，距C还有1站）
busTracker.nearestBusToStation("D") // 2
busTracker.nearestBusToStation("E") // 0（2号车就在E站）
busTracker.nearestBusToStation("F") // 1
busTracker.getBusLocation(1)        // "B"
busTracker.getBusLocation(2)        // "E"

解题思路

1. 站点映射：先把站点字符串解析成数组，建立站点名到下标的映射
2. 公交位置索引：记录每辆车所在站点的下标
3. 预处理最近距离：从右往左扫描，预处理每个站点右侧最近公交的距离
4. O(1) 查询：查询时直接返回预处理好的结果

Python 实现

class BusTracker:
    def __init__(self, station_list: str, bus_locations: dict):
        self.stations = station_list.split('-')
        self.station_to_idx = {s: i for i, s in enumerate(self.stations)}
        self.bus_locations = bus_locations
        
        # 预处理每个站点到最近公交的距离
        n = len(self.stations)
        self.nearest = [-1] * n
        min_bus_idx = float('inf')
        
        for i in range(n - 1, -1, -1):
            # 检查当前站是否有公交
            for bus_id, station in bus_locations.items():
                if self.station_to_idx[station] == i:
                    min_bus_idx = i
            
            if min_bus_idx != float('inf'):
                self.nearest[i] = min_bus_idx - i
    
    def nearestBusToStation(self, station_id: str) -> int:
        if station_id not in self.station_to_idx:
            return -1
        return self.nearest[self.station_to_idx[station_id]]
    
    def getBusLocation(self, bus_id: int) -> str:
        return self.bus_locations.get(bus_id, "")

复杂度分析

• 时间复杂度：预处理 O(n×m)，其中 n 是站点数，m 是公交数；查询 O(1)
• 空间复杂度：O(n) 用于存储预处理结果

面试技巧

这道题考查的是预处理优化查询的思想。面试时要注意：

• 先确认边界条件（站点不存在、公交不存在等情况）
• 讨论是否需要支持动态更新公交位置
• 如需支持更新，可考虑使用更复杂的数据结构

需要面试辅助服务？联系我们

• 📧 Email: [email protected]
• 📱 Phone: +86 17863968105

需要面试真题？ 立刻联系微信 Coding0201，获得真题。