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.

Triangle Minimum Path Sum

Return the minimum top-to-bottom path sum in a triangular array.

Constraints

• row i has length i + 1

Examples

Example 1

Input: ([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]],)
Output: 11

Explanation: Classic example.

Example 2

Input: ([[-10]],)
Output: -10

Explanation: Single negative row.

Hints

1. Fold the DP from the bottom row upward.

Two Dice Stopping Statistics

Return the probability that the 5-sided die wins and the expected number of rounds until at least one die shows 1.

Constraints

• Die A has faces 1..5; Die B has faces 1..6

Examples

Example 1

Input: ()
Output: (0.5, 3.0)

Explanation: Analytical probability and expectation.

Hints

1. Condition on the first stopping round.