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 .

- Piyush Kapoor September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rahul Sharma September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 0x0 October 10, 2013 | Flag
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.

- IdleMind September 06, 2013 | Flag Reply
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.

- IdleMind September 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What does arbitrarily large weight mean?

- alex September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

change the negative edge and positive to integretss

- Loganathan G September 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

please explain algo

- karan September 12, 2013 | Flag Reply
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...

- bigphatkdawg September 17, 2013 | Flag Reply
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...

- bigphatkdawg September 17, 2013 | Flag Reply
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)

- Zero2 July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 06, 2013 | Flag


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