Google Interview Question for Software Engineer in Tests






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

start from an arbitrarily node, do a bfs or dfs to find out the furtherest node, denote it as node a. O(n)
start from node a, do a bfs or dfs again to find out the furtherest node from node a, get the length len. O(n)
then the least height of the tree is interget part of (len+1)/2, and the root node is node b which is (len+1)/2 from node a.
total time complexity is O(2n)=O(n)
correct me if sth wrong

- songlj August 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good one .

- Anonymous August 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It seems working like a magic!
But, what's the logic behind?

- anonymous August 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good one.

Logic is : he is trying to find out the centre. So the arbitarily selcted node might be an inside node which has node distributed its both of the sides. Now using first bfs and selecting farthest element we are starting from a corner of the graph and now selecting farthest element from the corner which will give you diameter of graphs.

So finad diameter and the node which is diameter/2 distance away from node is the root node.

- Gaurav August 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The definition of the diameter of a graph is the maximum distance between any two nodes of a graph. How can that be found out if we start at an arbitrary node and stop on finding the furthest node from the arbitrarily chosen node?

- AC September 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As above comment, the part starting at arbitrary node and find the length is not clear. I will do BFS from a leaf. During the traversal, I will keep the records of the longest and the second longest distance to the leaves and the corresponding edges (direction) for every "branch node" (Node with degree > 2).

- Chen.Yangho October 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This works because this graph is 'acyclic'.

- annon October 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The graph is a tree since it has no cicles, so start at a random node and find the lowest leaf, then find the next lowest leaf. The path from the lowest leaf to the next lowest leaf has the root at the middle.

- Anonymous April 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

it is nlogn, since you take n to find the root, thus T(n)=2*T(n/2)+O(n).

- Anonymous May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

there's something wrong with the way you're finding the diameter of the graph... there's no known algorithm that can find the 2 furthest vertices in linear time.

- citisushi July 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here comes the logic , doing bfs from the arbitrary node gurantees to give you one end of the diameter because , while doing bfs once you come to a node in diameter , now its similar to starting of bfs from a point in diameter , so whichever end it is farther from it will print that node it the end (and all other nodes will be nearer that it otherwise those would have become the diameter)

- Geek January 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is actually not so simple to prove that it will be on diameter but I think it is true.
a) you start already on diameter. Then the node most far away from you must be on diameter, otherwise diameter is wrong (further node from "diameter" and the latest further node found is longer than the diameter).
b) you are not already on diameter. There must be a path to diameter though (it is connected). So the minimum path you can get from diameter is diam/2. In case you can find something else that is not part of diameter (otherwise by a) you would end in diameter) is larger or equal, than diameter can be improved at least by +1 length.

Both cases lead to a conclusion, that you will find a node on a diameter.

- mbriskar May 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Find the center of the tree. Delete all nodes of degree one. Repeat till you are left with one or two nodes...

- Anonymous August 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

meanwhile, i think this question is a little bit difficult for "SDE in tests", for SDE is a good question

- supersonglj August 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@supersonglj : you are a motherchod.....

- AC September 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lol AC

- Anonymous April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@AC hahahaha

- knownAnonymous May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually I was interviewed for SE in Test and the questions weren't any easier. And I got interviewed by both SEs and SETs. Yes, but they do ask you to extensively test the code that you write when you're interviewing for the SET position. Btw, SDET is a Microsoft thing. In Google it's SET.

- bp January 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Doesnt BFS or DFS have time complexity of O(N+E), where E=Nsquare for connected graphs(worst-case)?. Then net time complexity of this algo would be O(Nsquare)?
Let me know if i am correct on this...

- Anonymous September 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

the graph is connected and doesn't contain cycles. Thus the number E of edges is exactly V - 1.

- marco September 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the graph is connected and doesn't contain cycles. Thus the number E of edges is exactly V - 1.

- marco September 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//let u be any node in the graph
//consider 2 queues BFSQ and TreeQ
//I am trying to collect each node from graph in BFS way and enter each node in the tree in BFS way so that the height of the tree is minimized

the Algo
===========================================================================

BFSQ.enqueue(u)

while(BFSQ.isnotempty())
{

- Anonymous September 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we are given a tree and we have to find the maximum distance between any two point than also we can apply the same logic: we pick an arbitary point apply bfs/dfs to find the farthest point than we apply dfs/bfs on the farthest point and find the point farthest from it.But how to prove its correctness??

- Anonymous April 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More