Dice Roll Simulation

Dice Roll Simulation

What is this problem about?

The Dice Roll Simulation interview question asks you to find the number of distinct sequences of $n$ dice rolls such that no number $i$ appears more than rollMax[i] times consecutively. For example, if rollMax[1] = 2, you cannot have [1, 1, 1] in your sequence. Return the answer modulo $10^9 + 7$.

Why is this asked in interviews?

This "Hard" problem is a favorite at Akuna Capital because it tests your mastery of Dynamic Programming. It evaluations whether you can define a state that captures all necessary constraints—in this case, not just the number of rolls, but also what the last roll was and how many times it has repeated. It’s a test of "State Expansion."

Algorithmic pattern used

This is a 3D Dynamic Programming problem. State: dp[i][last_val][count]

• i: Number of rolls completed.
• last_val: The value of the last die roll (1-6).
• count: How many times last_val has appeared consecutively so far. Transition:
• For the next roll, try every value $v$ from 1 to 6.
• If $v == last\_val$: If count + 1 <= rollMax[v], move to dp[i+1][v][count+1].
• If $v e last\_val$: Move to dp[i+1][v][1].

Example explanation

$n=2$, rollMax = [1, 1, 2, 2, 2, 2].

1. Roll 1: 6 possibilities, all with count 1.
2. Roll 2:
   • If Roll 1 was '1': next roll can be 2, 3, 4, 5, 6. (Next cannot be '1' because rollMax[1]=1).
   • If Roll 1 was '3': next roll can be 1, 2, 3, 4, 5, 6. (Next can be '3' because rollMax[3]=2). Total valid sequences are summed up.

Common mistakes candidates make

• Modulo arithmetic: Forgetting to apply the modulo at every addition, leading to overflow.
• State explosion: Not realizing that count is bounded by the maximum value in rollMax (usually small, like 15), keeping the DP table manageable.
• Base Case: Incorrectly initializing the first roll.

Interview preparation tip

When a DP problem has a "consecutive" constraint, your state must include "how many of the current type I just placed." This is a standard template for sequence-based DP.