## Google Interview Question for SDE1s

• -3

Country: India

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

Question is not clear

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

Topological sorting will print it properly ?

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

You're assuming that the graph is a Directed Acyclic Graph(DAG). I think the interviewer meant a graph in general.

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

Not sure I understand what you mean by "edges don't intersect and they seem ordered". Can you clarify? What happens for example in a complete graph of 4 nodes?

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

You mean 5 nodes? 4 nodes you can draw (place 4th vertex inside of triangle formed by first 3)

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

``````public void drawGraph(node n, graphics g) {
if (n == null)
return;

Queue<Node> q = new Queue<Node>();

g.drawSmallCircle(n.point);
n.visted = true;
q.enQueue(n);

while (!q.isEmpty()) {

n = q.deQueue();
for (Node a : n.adjNodes) {
if (!a.visted) {
g.drawSmallCircle(a.point);
g.drawLine(n.point, a.point);
a.visted = true;
q.enQueue(a);
}
}
}
}``````

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

This will not work for a completetly connected graph and several other cases

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

Question is not clear.
1) printing in order topological sort: do a DFS, order the vertices by departure times(desc)
2) edges should not intersect, finding if a graph is planar

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.