Bloomberg Interview Question: Bus Tracker

Problem

You are building a bus tracking website. Buses move between stations in one direction (left to right). A bus is always exactly at a station (never between stations).

Implement:

class BusTracker {
  // stationList is a list of stations delimited by a hyphen (-)
  // e.g. "1-2-3-4-5" corresponds to 1 -> 2 -> 3 -> 4 -> 5
  // buses only move left-to-right
  // busLocations maps busId -> stationId
  constructor(stationList, busLocations) {}

  // return how many stops away the nearest bus is from the given station
  // if all buses are to the left of stationId, return -1
  nearestBusToStation(stationId: string): number { return -1; }

  // return the stationId where the given bus currently is
  getBusLocation(busId: number): string { return ""; }
}

Example

Stations: A-B-C-D-E-F-G-H-I
Buses: {1: "B", 2: "E"}

nearestBusToStation("A") -> -1
nearestBusToStation("B") -> 0
nearestBusToStation("C") -> 1
nearestBusToStation("D") -> 2
nearestBusToStation("E") -> 0
nearestBusToStation("F") -> 1
getBusLocation(1) -> "B"
getBusLocation(2) -> "E"

Approach

• Build a station -> index map.
• Convert each bus location into its station index.
• Precompute (right-to-left) the distance from each station to the nearest bus at-or-to-the-right.

Python (reference)

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

        bus_indices = set(self.station_to_idx[s] for s in bus_locations.values() if s in self.station_to_idx)
        next_bus = None

        for i in range(n - 1, -1, -1):
            if i in bus_indices:
                next_bus = i
            if next_bus is not None:
                self.nearest[i] = next_bus - i

    def nearestBusToStation(self, station_id: str) -> int:
        idx = self.station_to_idx.get(station_id)
        if idx is None:
            return -1
        return self.nearest[idx]

    def getBusLocation(self, bus_id: int) -> str:
        return self.bus_locations.get(bus_id, "")

Complexity

• Preprocessing: O(n + m)
• Query: O(1)
• Space: O(n)

Need interview help? Contact OA VO Service

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

Need real interview questions? Contact WeChat: Coding0201 to get the questions.