You're creating a website where people can track the bus 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 {// stationList 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：给定按顺序用 - 连接的站点字符串，以及每辆车当前停靠的站点。nearestBusToStation 要返回从指定站点往前（向右）走，最近能遇到的公交还相隔多少站，如果所有车都在它左边则返回 -1。getBusLocation 根据 busId 直接查出当前所在站点。实现时常见做法是：先把站点映射成下标，记录每辆车所在的下标，再从右往左扫一遍，预处理“该站右侧最近公交距离”，查询时即可 O(1) 返回。
Bloomberg Interview Question: Word Search on Grid – 网格单词搜索
Problem Description
Given a 2-D array of characters as a board, and a string word as the target,
write a function to check if the target word can be found on the board.
The word has to be composed by a series of adjacent characters
(horizontally or vertically neighbors) on the board, and one character
can only be used once.
Sample inputs - Expected outputs
Given board is:
board = {['B', 'C', 'F', 'E'],
['E', 'A', 'B', 'L'],
['B', 'C', 'D', 'O'],
['E', 'B', 'M', 'O'],
['R', 'G', 'D', 'E'],
}
If word = "BLOOMBERG", return true (it can be composed from the board).
If word = "BOB", return false (cannot be composed by any path).
If word = "BEABLE", return true (it can be composed from the board).
这是典型的“单词搜索”题：给定字符矩阵和目标单词，判断能否通过上下左右相邻的格子按顺序拼出该单词，每个格子在一次搜索路径中只能使用一次。常规解法是 DFS 回溯：从所有与首字母相同的格子作为起点，递归尝试四个方向扩展下一个字符，用 visited 标记避免重复使用格子，只要有一条路径完整匹配整条单词就返回 true。
正文完
