Compute triangle min path and dice stopping stats
Company: Agoda
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: nan
Interview Round: Technical Screen
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.
Quick Answer: This composite question evaluates dynamic programming and algorithmic optimization via the triangle minimum path problem and probability, stopping-time analysis and Monte Carlo simulation through the two-dice experiment, testing competencies in DP, discrete probability, expected-value reasoning and empirical estimation.
Triangle Minimum Path Sum
Return the minimum top-to-bottom path sum in a triangular array.
Examples
Input: ([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]],)
Expected Output: 11
Explanation: Classic example.
Input: ([[-10]],)
Expected Output: -10
Explanation: Single negative row.
Input: ([],)
Expected Output: 0
Explanation: Empty triangle.
Input: ([[1], [2, 3]],)
Expected Output: 3
Explanation: Two rows.
Hints
- 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
Input: ()
Expected Output: (0.5, 3.0)
Explanation: Analytical probability and expectation.
Hints
- Condition on the first stopping round.