Google Interview Question for Software Engineer / Developers
- 4of 4 votes
Given a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.
Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5
Edit: Thanks, wangchenClark0512, forgot about C to D- djway August 18, 2016 in United States
Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.
Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs
Interview Type: Phone Interview
Open Chat in New Window