## Amazon Interview Question

Software Engineer / Developers**Country:**United States

Probablity

All paths from A to S and S to B with Nmins(BFS till time reaches N mins) / total number of paths from A-B

For simplicity let assume that there are K ways from A to B that you can reach in N or less minutes. From interviewer you need to clarify also constrains like loops in paths, etc.

In Q ways from K there are Starbuckses. As a result probability will be

P= Q/M.

As reference of finding K ways please see wikipedia URL:

en.wikipedia.org/wiki/K_shortest_path_routing

Weighted DiGraph, with A,Starbucks,B as vertices (probably has other nodes as well) and time as weight.

- arht January 09, 2015Probablity

All paths from A to S and S to B with adding the time not exceeding N mins/would be number of paths from A-B