Agoda·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Had a software engineering interview at Agoda with two pretty different questions back to back. One was a classic DP problem, the other was a probability/simulation question that threw me a bit. Nothing about the experience felt particularly warm or cold, just technical.

Questions Asked (2)

Given a triangular array where each row has one more element than the last, find the minimum path sum from the top to the bottom. At each step you can move to the element directly below or one position to the right in the next row.

Algorithms & Data Structures

Author's notes

Classic DP, and I knew it was DP pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose a dynamic programming solution that computes the minimum path sum from top to bottom. Explain how you can optimize space by updating the triangle in place or using a 1D array, and analyze the time and space complexity.

Pro tip: Mention that you can solve it bottom-up to avoid extra space for handling boundaries, and that modifying the input in place is acceptable if the interviewer allows it. This shows awareness of practical constraints and optimization.

1. Clarify the problem

Confirm the movement rules (down or down-right), input format, and expected output. Ask about edge cases like empty triangle or single element.

2. Choose an approach

Decide between top-down and bottom-up DP. Explain that bottom-up is simpler because it avoids boundary checks and naturally accumulates minimum sums.

3. Define the DP state and recurrence

For bottom-up, let dp[i][j] be the minimum path sum from (i,j) to the bottom. Recurrence: dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]).

4. Optimize space

Show how to reduce space to O(n) by using a 1D array or modifying the triangle in place, updating from bottom to top.

5. Analyze complexity and test

State time complexity O(n^2) where n is the number of rows, and space complexity O(n) or O(1) if in-place. Walk through a small example to verify.

Key Points to Mention

Dynamic programming approach with optimal substructure
Bottom-up vs top-down trade-offs
Space optimization using 1D array or in-place modification
Time complexity O(n^2) and space complexity O(n) or O(1)
Handling edge cases such as empty triangle or single row
Clear explanation of the recurrence relation and initialization

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

You have a 5-sided die and a 6-sided die. Each round you roll both. The process stops when at least one die shows 1. If only the 5-sided die shows 1 it wins, if only the 6-sided shows 1 it wins, and if both show 1 it's a tie. Find the probability that the 5-sided die wins, the expected number of rounds until stopping, and implement a Monte Carlo simulation to estimate both.

Algorithms & Data StructuresA/B Testing & Experimentation

Author's notes

This one took me by surprise.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Break the problem into three parts: first compute the probability that the 5-sided die wins using geometric series or conditional probabilities, then compute the expected number of rounds until stopping using the per-round stopping probability, and finally outline a Monte Carlo simulation that estimates both quantities by repeatedly simulating the process. Emphasize the independence of the dice and the memoryless property of the stopping condition.

Pro tip: When explaining the simulation, mention how you would validate it against the analytical results and discuss the trade-off between number of trials and accuracy, showing you understand both theory and practical implementation.

1. Define per-round outcomes

List all possible outcomes of rolling both dice and identify which outcomes lead to stopping, which die wins, and the probabilities of each outcome.

2. Compute win probability analytically

Use the per-round probabilities to set up an equation for the probability that the 5-sided die wins, considering that the process may continue for multiple rounds.

3. Compute expected number of rounds

Use the geometric distribution formula for the expected number of trials until the first success, where success is the event that at least one die shows 1.

4. Design Monte Carlo simulation

Outline a simulation loop that rolls both dice until stopping, records the winner, and repeats many times to estimate the win probability and average number of rounds.

5. Validate and discuss results

Compare simulation estimates with analytical results, discuss sources of error, and explain how to choose the number of trials for desired precision.

Key Points to Mention

Independence of dice rolls and the memoryless property of the stopping condition.
Per-round probabilities: P(5-sided wins) = (1/5)*(5/6) = 1/6, P(6-sided wins) = (4/5)*(1/6) = 2/15, P(tie) = (1/5)*(1/6) = 1/30, P(continue) = (4/5)*(5/6) = 2/3.
Analytical win probability for 5-sided die: (1/6) / (1 - 2/3) = 1/2.
Expected number of rounds: 1 / (1 - 2/3) = 3.
Monte Carlo simulation: use a loop to simulate rounds, count wins and total rounds, and compute averages.
Validation: compare simulation output with analytical results and discuss convergence and confidence intervals.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.