Compute triangle min path and dice stopping stats

You are given two independent interview questions.

1) Triangle minimum path sum (DP)

Given a triangular array triangle with n rows, find the minimum path sum from the top to the bottom.

• You start at triangle[0][0] .
• From row i , column j , you may move to row i+1 at column j or j+1 .
• Return the minimum possible sum along any valid top-to-bottom path.

Input: A list of lists, where row i has length i+1.

Output: An integer (or numeric) minimum path sum.

Constraints (typical): 1 <= n <= 2000, values may be negative/positive.

2) Two dice stopping problem + Monte Carlo

There are two fair dice:

• Die A has faces {1,2,3,4,5} (a 5-sided die).
• Die B has faces {1,2,3,4,5,6} (a 6-sided die).

The experiment proceeds in rounds. In each round, you roll both dice once.

• The process stops at the first round where at least one die shows 1 .
• In the stopping round:
  • Die A wins if A=1 and B≠1 .
  • Die B wins if B=1 and A≠1 .
  • It is a tie if A=1 and B=1 .

Answer the following:

1. What is the probability that the 5-sided die (Die A) wins ?
2. What is the expected number of rounds until the process stops?
3. Implement a Monte Carlo simulation to estimate (1) and (2), and discuss how many trials you would run to get a stable estimate.