Amazon Online Assessment Coding Interview Question: Virus Spread in a Tree of Cities

A country is represented as a tree of cities originating from a single root city.

Each city may be connected to one or more neighboring cities.

A virus starts spreading from city Cm.

Every day, the virus spreads from an infected city to all directly connected neighboring cities.

Given two cities Cm and Cn, determine how many days it will take for the virus to spread from Cm to Cn.

Input

root = C1
src = C7
dst = C8

Output

5

Explanation

Day 0: C7
Day 1: C3, C11, C12
Day 2: C6, C1
Day 3: C2
Day 4: C4, C5
Day 5: C8, C9, C10

C8 becomes infected on Day 5.
Therefore return 5.

This problem asks for the number of days it takes a virus to spread from a source city to a destination city in a tree-shaped country. Since the virus reaches all adjacent cities one step per day, the answer is simply the shortest path distance between the two cities in the tree. A typical solution is to build parent links or convert the tree into an undirected graph, then run BFS from the source and return the level when the destination is first reached.