How should I practice Frog Position After T Seconds?

Start by reading the full statement, solve the visible examples, then compare the pattern against related InMobi phone screen problems in FastPrep.

Is Frog Position After T Seconds associated with InMobi?

FastPrep tags this as a InMobi phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Frog Position After T Seconds

Learn this problem

● Medium

InMobiFULLTIMEPHONE SCREEN

Problem statement

An undirected tree has n nodes labeled from 1 to n. A frog starts at node 1 at time 0.

Each second, the frog follows these rules:

If its current node has one or more neighbors it has not visited, it jumps to one of those neighbors with equal probability.
If every neighbor has already been visited, it remains at the current node.

The tree is supplied as an edge list, where every row [u, v] represents one undirected edge. Return the probability that the frog is at target after exactly t seconds.

Function

frogPosition(n: int, edges: int[][], target: int, t: int) → double

Examples

Example 1

n = 7edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]]target = 4t = 2return = 0.16666666666666666

The frog chooses node 2 from the root with probability 1/3, then chooses node 4 from node 2 with probability 1/2. Their product is 1/6.

Example 2

n = 4edges = [[1,2],[1,3],[1,4]]target = 4t = 2return = 0.3333333333333333

The frog reaches leaf 4 after one second with probability 1/3. Since the leaf has no unvisited neighbor, it stays there for the second second.

Constraints

1 <= n <= 100
edges.length = n - 1
Every edge has exactly two endpoints in 1..n.
edges forms a connected, undirected tree.
0 <= t <= n
1 <= target <= n