Minimum Time Path in Tree | Dataford Interview Questions

Minimum time path with tasks: in an unweighted undirected tree, from a start node visit a set of mandatory task nodes in any order and then reach a destination in minimum time.

Asked in the OA stage. Implement min_time(n, edges, start, tasks, destination), where nodes are 0 through n - 1, edges contains the tree edges, and tasks is a list of required nodes. Return the minimum number of edges traversed.

Example: n = 5, edges = [[0,1],[1,2],[1,3],[3,4]], start = 2, tasks = [4], destination = 0 returns 6, because the required subtree has four edges and the start-to-destination path is traversed once.

Constraints: 1 <= n <= 5000; edges has n - 1 pairs; the graph is a connected tree; node IDs are valid; tasks contains no duplicates.

Constraints

1 <= n <= 5000
0 <= start, destination < n
0 <= len(tasks) <= n
tasks contains no duplicate node IDs
edges contains exactly n - 1 pairs
The graph is a connected, undirected tree

Function Signature

def min_time(n, edges, start, tasks, destination):

Your question is Minimum Time Path in Tree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem