How should I practice Amount of Time to Infect a Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Amount of Time to Infect a Tree associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Amount of Time to Infect a Tree

Learn this problem

● Medium

AmazonNEW GRADONSITE INTERVIEW

See Amazon hiring insights

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.

Example 3

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

Star graph with 10 nodes, start at a leaf (node 5). Infection spreads to center (1) at minute 1, then to all other leaves at minute 2. Answer is 2.

Constraints

The given edges form a tree.
Each edge string has the format "u->v".
start is a city in the tree.