FastPrep
Problem

Minutes to Infect Tree

Learn this problem
SASavantLabsFULLTIMEONSITE INTERVIEW

Problem statement

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.

Function

minutesToInfectTree(graph: String[], start: int) → int

Examples

Example 1

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

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

Example 2

graph = ["1->2", "2->3", "3->4"]start = 2return = 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
checking account