Bloomberg VO 面试真题解析：Bus Tracker（数组 / 哈希表 / 距离查询）

You are creating a website where people can track buses and figure out when to go to the station. The buses move between the stations in one direction. The goal is to find the station any bus is currently at or find how many stops away the nearest bus is to a requested station. Buses are never between stations; they are only stopped at a station.

Your task is to implement this class:

class BusTracker {// station list is the list of stations delimited by a hyphen (-)
    // e.g. the station list can look like 1-2-3-4-5 and this will correspond to a map that looks like 1 -> 2 -> 3 -> 4 -> 5
    // because buses only move in one direction, from left to right
    // busLocations is the current list of buses and the stations they are currently at
    // these two fields provide the input to figure out the next two functions
    constructor(stationList, busLocations) {}

    // given the buses flow in one direction, find how many stops away
    // the next bus is to the provided station
    public nearestBusToStation(stationId: string): number {return -1;}

    // given a bus id, return the station the bus is currently at
    public getBusLocation(busId: number): string {return "";}
};

Sample inputs – Expected outputs

For station map: "A-B-C-D-E-F-G-H-I"
And bus positions: {1: "B", 2: "E"}

busTracker.nearestBusToStation("A") // -1
busTracker.nearestBusToStation("B") // 0
busTracker.nearestBusToStation("C") // 1
busTracker.nearestBusToStation("D") // 2
busTracker.nearestBusToStation("E") // 0
busTracker.nearestBusToStation("F") // 1
busTracker.nearestBusToStation("G") // 2
busTracker.nearestBusToStation("H") // 3
busTracker.nearestBusToStation("I") // 4
busTracker.getBusLocation(1) // B
busTracker.getBusLocation(2) // E

这道题需要实现一个 BusTracker 类，核心是把站点字符串按“-”切分成有序线路，并用哈希表记录每辆公交车当前所在站点。查询某个站点到最近公交车的距离时，只需要利用站点在路线中的顺序，找到该站点右侧最近的公交车即可；如果站点左侧没有更早的公交车，则返回 -1。查询公交车位置则可以直接通过 busId 在映射表中 O(1) 获取。整体思路适合用数组保存站点顺序、用字典保存公交位置，并配合一次线性扫描或预处理来完成距离查询。