## Google Interview Question for Software Analysts

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
4
of 6 vote

Assuming that the weight of a path is simply the sum of edge weights , answer should be (d) , by using any shortest path graph algorithm like floyd warshall .

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

@ piyush kapoor u are right answer is d ... but what does it mean "determining whether there are paths of arbitrarily large weight " please explain..

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

it means that there is a positive weight cycle. hence, there is no limit to the weight of paths using this cycle repeated times.

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

I don't really understand what the term "arbitrarily large weight" is implying. However, Floyd-Warshall is an all-pairs shortest paths algorithm. If we are interested in all-pairs shortest paths then we can do better by using Johnson's algorithm whose time complexity is O(V^2 lg V + VE). In contrast, single-source shortest path can be done in O(VE) using Bellman-Ford algorithm. It can handle the scenario where graph contains negative-weight cycles.

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

"arbitrarily large weight" not shortest path...
1 -- 2
| /
3
if the edge (1, 2) is 1; (1, 3) is 2; (2, 3) is 100.
And I ask if there exists a path of length 100. Floyd and Johnson will never work...

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

If we change positive edge weights into negative edge weights, change negative edge weights into positive edge weights, then this problem is equal to find a path with arbitrarily small weight, there is an algorithm called "BellmanFord" can do this.

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

When using BellmanFord, in sparse graph O(n^2) can be achieved, in dense graph O(n^3) can be achieved.

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

What does arbitrarily large weight mean?

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

it means that there is a positive weight cycle. hence, there is no limit to the weight of paths using this cycle repeated times

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

change the negative edge and positive to integretss

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

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

If supremum{weights of edges} has no upper bound, then the graph is an infinite graph...

So it would take infinite amount of time to check this...

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

If supremum{weights of edges} has no upper bound, then the graph is an infinite graph...

So it would take infinite amount of time to check this...

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

If we just have to detect cycles with positive weight then I think DFS should be enough. Just keep storing the nodes visited so far summing the edge weights and when you hit a node that is already visited there is a cycle. Now, just check if the total weight is positive and if it is then we got our answer.

Time complexity: O(n)

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

Yes, it is quite surprising if Google asks this. Sounds more like homework, to be honest.

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.