Katkat
Back

Compute triangle min path and dice stopping stats

AgodaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.