Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

Out of the following input:
Bus 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 bi-directional Dijkstra, if the graph is not time-dependent.

Comment hidden because of low score. Click to expand.
2
of 2 vote

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).

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex
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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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 multi-line 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex
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 :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex
yeah, agreed. split in run time. that's just what BFS do.
As for the connection, probably just different interpretations of models.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@zyfo2. The same for me. Thank you!

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.