Asked for SDE 2 interview.
An employee needs to get to work from home. There is a range that the employee can walk in any direction. There are bus stations on the way to the destination which can the employee can walk to if it is within the walking range and board the bus and get off at the next station. Transit buses can be at the same point or they can be at away from each other. If the next bus station is not at the same spot, then the employee can board the next bus if it is within the walking range. Find out if the employee can get to work or not.
For the sake of this question, assume there are no cycles that can form with the bus station and there exists only a single bus station route.
Ex: Range that the employee can walk at any point: 5
Distance between home to bus station 1 is 1.Employee can take the bus from station 1 and go to station 2. The next bus is that the employee can take is bus station 3 at distance 2. Since it is within walking distance range of 5, he can walk to bus station 3 and take the bus to reach bus station 4. He can then take next bus at the same bus station that drops directly at work.
(the points don't necessarily need to have common x or y axis shared between them. It's just easy to illustrate this way as an example)
* Home
bus station (1)*--------------------*bus station (2)
* bus station (3)
|
|
|
|
work *------------------------* bus station (4)
Important note: there was no defined input parameters for this question. It is upto the programmer to pick and choose data structures that best fit the description of the problem and that will help reach the solution.
What would be the best way to solve this?