I was in a trading firm interview, I was asked this question,
you are travelling accross the state in a buses, the buses can stop at any C possible cities and you need to find a way to go from city a to city b. There are total B buses, each of which travels between two cities. All buses travel on a daily bases, for example each bus x leaves some city c1 on day d1 and arrives at another city b1 on another day d2 (d2>d1). Assume that if you arrive at a city on day d, you can catch any bus leaving the city on day d or after.
you are given a1, b1,d1, and d2 for B buses. describe an algorithm that determines whether there exist a route from city a to city b in no more than D days, and analyze the run time.
I was initially try to model the problem in to shortest path algorithm but I could not figure out at that moment, I screwed the interview.
See Question&Answers more detail:os