## 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 States`Input: 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

Rep**juanajcox4**, Python Developer at Axiom SourcesI have 2 years of experience in designing and implementing computer algorithms or models for creating, displaying, and processing various ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

@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