FastPrep
Problem

Minutes to Infect Tree

SavantLabsFULLTIMEONSITE INTERVIEW

You are given a tree of cities. Each city has an integer name. The tree edges are given as strings in the format "u->v", meaning city u is connected to city v.

At minute 0, an infection starts at city start. Each minute, every currently infected city infects all adjacent uninfected cities.

Return the number of minutes needed for the entire tree to become infected.

Examples
01 · Example 1
graph = ["1->5", "1->3", "5->4", "4->9", "4->2", "3->10", "3->6"]
start = 3
return = 4

The farthest cities from 3 are 9 and 2, each at distance 4. Therefore all cities are infected after 4 minutes.

02 · Example 2
graph = ["1->2", "2->3", "3->4"]
start = 2
return = 2

City 1 is infected after 1 minute, city 3 after 1 minute, and city 4 after 2 minutes.

Constraints
  • The given edges form a tree.
  • Each edge string has the format "u->v".
  • start is a city in the tree.
drafts saved locally
public int minutesToInfectTree(String[] graph, int start) {
  // write your code here
}
graph["1->5", "1->3", "5->4", "4->9", "4->2", "3->10", "3->6"]
start3
expected4
sign in to submit