djway
BAN USER- 4of 4 votes
AnswersGiven 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.
Example: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 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 - 7of 7 votes
AnswersYou are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.
Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)
Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.
Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)
The total run-time after returning everything should be O(n).
Examples:
- djway in United StatesInput: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 3of 3 votes
AnswersGiven a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's
- djway in United States for None
Example:
findStrings(3) returns 19
since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb
and the invalid combinations are:
abb,bab,bba,bbb,bbc,bcb,cbb,ccc| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
Repjuanajcox4, Python Developer at Axiom Sources
I have 2 years of experience in designing and implementing computer algorithms or models for creating, displaying, and processing various ...
RepHelanZelda, Consultant at Advent
HelanZelda from Atlanta, GA, United States. I have a passion for exploring/sharing new ideas and experiences throughout the interdisciplinary ...
@mrsurajpoudel.wordpress.com The interviewer told me not to worry about cycles for now, so I probably did not get far enough for the followup question.
- djway August 19, 2016