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"
You must design a BusTracker that knows the ordered list of stations and where each bus currently is. nearestBusToStation returns the minimum number of forward stops from a given station until you meet any bus (or -1 if all buses are behind it). getBusLocation is just a lookup from bus id to its station. A typical implementation precomputes a station-index map, stores bus positions as indices, and for each station precomputes the next bus ahead using a right-to-left sweep.
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).
This is a classic word-search problem. From each cell you may move up/down/left/right to build the word, and each cell can be used at most once in a path. The solution is DFS with backtracking: for every starting cell that matches the first letter, recursively try neighbors for the next letter while marking visited cells, and succeed if you consume the whole word.
