Google Interview Question
Software EngineersCountry: United States
it's an interesting and actually a practical one.
the way I came up is that:
form a graph using these lists, node as station and do BFS.
but it's not a normal graph. you have to store bus numbers in the node itself and keep track of your current bus number in BFS. so when do BFS, you meet a station with multiple bus numbers, you traverse all of them and when current bus number changes your switch++.
or to make it more clear, you replicate the nodes for nodes having multiple bus numbers. so a node is essentially a bus station binding a bus number.
also a small trick to cut possible BFS branches, you'll have at most n switches (n is the totally number of bus numbers) and you never switch back to a previous bus number(cause only switches count in this question).
1. create a graph where nodes are stations and edges are labeled with bus number.
2. perform a BFS starting from the "start station" and keeping track for each node explored, how many bus switches have been made. when reaching the end node (possibly multiple times) only save the least amount of switches.
3. return the number of switches.
@zyfo2. It's definitely possible to use BFS in here, but the model in this case is far from reality. E.g. what if the transfer from Bus 1 to Bus 2 is open only from 1pm to 3pm. In the model when station c is represented by a single node, it would be a lot of logic to support this.
Also, if the data looks like this:
Bus 1: abcde
Bus 2: fgcdh
Bus 3: ijcdkl
, which of the bus lines will be stored in the nodes c an d? Or in the link between c and d?
@Alex
that's exactly why I voted down your answer
You didn't handle that example in your solution.
But in my solution. we can store the all the bus numbers in one node say in node c and d in your example, we need to store [1,2,3] there. and we also keep track of the current bus number we are on. and when going to another bus line, switch++.
another way is to replicate node c and d three times and each of them is bond with the bus number.
I believe I made it clear in my answer.
@zyfo2. I'm not sure why the example won't work in my solution. It works every time in real life, when I change buses :)
Input:
Bus 1: abcde
Bus 2: fgcdh
Bus 3: ijcdkl
Graph:
(1)>(2)>(3)>(4)>(5)
 
(6)>(7)>(8)>(9)>(10)
\ \
(11)>(12)>(13)>(14)>(15)
A note: there are also links (3)>(13), (4)>(14).
Station to node mapping:
a=>(1)
b=>(2)
c=>(3), (8), (13)
d=>(4), (9), (14)
e=>(5)
f=>(6)
g=>(7)
h=>(10)
i=>(11)
j=>(12)
k=>(14)
l=>(15)
The issue of your solution (when we don't split the station for each line, and keep several lines in a node link), is that if we traverse the graph as in real life (when the user rides only one bus at the current moment), while traversing we have to effectively split the multiline station into several branches. If we traverse pretending the user rides several lines at the current moment, we have to find intersection of several lines every time we move to the next stations.
@Alex
I got your idea.
you represent the same station by different numbers which is kind of misleading.
but, I have a question. For station C in your last example, do you also have to connect 3 and 13 since they are the same station and you need only one switch from line 1 to line 3? and for station D do you have to connect 4 and 14?
if so, I will form a kind of very complex graph if the intersection station have a lot of bus lines. you probably need to connect every two of them. also you need extra storage of node to ID mapping to check. though may not be a problem, but a little bit waste of memory and time.
my idea is basically the same. for your example
Bus 1: abcde
Bus 2: fgcdh
Bus 3: ijcdk
a[1] f[2] i[3]
  
b[1] g[2] j[3]
\  /
c [1,2,3]

d [1,2,3]
/  \
e[1] h[2] k[3]
the int list in [] are bus lines the station has.
when BFS traversing from one stop to next, we always keep track of the current line number.
and when meeting intersection station, we traverse all line number in the list and we only do switch++ when changing current line number.
Is that clear?
I think this is a little bit easier to understand and saves memory.
Please correct me if I got anything wrong :)
@zyfo2. Regarding (3)>(13) and (4)>(14). That's correct. Earlier I edited my post a few times, and added a note about the links.
Station to nodes mapping is not used while traversal. It takes some memory, but not a lot.
That's correct. It's a complex graph. But in real life it's of the same complexity.
I see that your solution is similar to mine and better regarding space, but the complexity isn't eliminated by it. The great complexity of transit graphs is just moved to the run time. The traversal algorithm effectively transforms your graph to mine. So, I think it's worth to keep the graph a bit more complex (and closer to reality) but keep the algorithm as simple as possible.
@Alex
I dont quite get this "The great complexity of transit graphs is just moved to the run time"
I dont see why my algorithm makes it more complex. It's just the same BFS which takes every line in the list as a node to traverse. I believe it's the same complexity.
And I believe in my real life, I see stations on bus stops as a list. I don't need to connect every two of them. All I need to know is that this stop has a certain list of bus lines. and I only need to switch if I want to go to a stop that's not my current line.
you connecting every two of them seems kind of redundant to me.
@zyfo2. Regarding moving complexity to run time. E.g.
Bus1: abcde
Bus2: abcdf
Bus3: abcdg
The graph is:
e
abcd/f
\g
The user departs from a. We have to check what lines are stored at node a, and for each of the lines, we add a new node in BFS: (a/Bus 1, a/Bus2, a/Bus3). So, we have effectively split the graph, but at run time.
I see. It may be looking redundant for bus stops which don't have transfer paths physically. Train stations with transfer tunnels may be better examples. And it's not necessary we have to connect nodes at the station each to each. We can just model those tunnels, e.g. a circular tunnel that has platforms to many train lines.
Out of the following input:
 Alex December 01, 2017Bus 1: a>b>c>d
Bus 2: c>e>f>g
we can create two independent chains of nodes:
(1)>(2)>(3)>(4)
(5)>(6)>(7)>(8)
Weights of all the edges (1>2, 2>3, ..., 7>8) gets set to 0.
Then, since we know that station c is the source of two nodes, we connect the nodes with a transfer link 3>5:
(1)>(2)>(3)>(4)
...................\
.....................(5)>(6)>(7)>(8)
The cost of the transfer link gets set to 1.
After that, we do Dijkstra expansion in the graph. Or bidirectional Dijkstra, if the graph is not timedependent.