Frog Position After T Seconds

Frog Position After T Seconds

What is this problem about?

The Frog Position After T Seconds coding problem involves a tree with $n$ vertices. A frog starts at vertex 1. At each second, the frog jumps to an unvisited adjacent vertex with equal probability. If it cannot jump anywhere (it's at a leaf node) or if $t$ seconds have passed, it stays where it is. You need to calculate the probability that the frog is on a specific target vertex exactly after t seconds.

Why is this asked in interviews?

This is a "Hard" problem asked by Google to test a candidate's ability to combine Graph Traversal (BFS/DFS) with Probability calculations. It requires careful state management: tracking time, tracking visited nodes, and calculating compound probabilities. It also includes a subtle "waiting" condition that traps many candidates.

Algorithmic pattern used

This problem uses Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the tree and calculate probabilities.

1. Start at node 1 with probability 1.0 and time 0.
2. In each step, find the number of unvisited neighbors ($k$).
3. If $k > 0$, the probability of moving to each neighbor is current_prob / k.
4. If you reach the target node:
   • If time is exactly $t$, return the probability.
   • If time is $< t$ but it has NO unvisited neighbors (it's a leaf), the frog stays there forever. Return the probability.
   • If time is $< t$ and it HAS unvisited neighbors, the frog will jump away. Return 0.

Example explanation

Tree: 1-2, 1-3, 1-7, 2-4, 2-6, 3-5. Target = 4, t = 2.

1. Start at 1. Prob = 1.0. Neighbors: 2, 3, 7. ($k=3$).
2. Jump to 2, 3, 7. Each has prob $1/3$. Time = 1.
3. Target is 4. We are at node 2. Prob = 1/3.
4. From 2, neighbors are 4, 6 (1 is visited). ($k=2$).
5. Jump to 4, 6. Prob for 4 becomes $(1/3) imes (1/2) = 1/6$. Time = 2.
6. Reached target 4 at exactly time 2. Result: 1/6 (0.1666...).

Common mistakes candidates make

• Leaf Node Trap: Assuming that if you reach the target before time $t$, the probability is 0. If it's a leaf node, the frog stays there, so the probability is valid.
• Revisiting Nodes: Forgetting to mark nodes as visited, leading to infinite bouncing between nodes.
• Floating Point Math: Not using double precision for the probability calculations, leading to slight inaccuracies.

Interview preparation tip

In probability problems on graphs, pass the probability down as a parameter in your DFS/BFS. Always clarify the "staying" conditions—does the actor stop moving when they hit a dead end, or do they fail the condition?