How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a nan difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Agoda.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Agoda during technical interviews.

Compute triangle min path and dice stopping stats

Quick Overview

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:

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

Quick Overview

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:

What is the probability that the 5-sided die (Die A) wins ?

What is the expected number of rounds until the process stops?

Implement a Monte Carlo simulation to estimate (1) and (2), and discuss how many trials you would run to get a stable estimate.

Compute triangle min path and dice stopping stats

Quick Overview

1) Triangle minimum path sum (DP)

2) Two dice stopping problem + Monte Carlo

Submit Your Answer

Compute triangle min path and dice stopping stats

Quick Overview

1) Triangle minimum path sum (DP)

2) Two dice stopping problem + Monte Carlo

Submit Your Answer