Shortest Impossible Sequence of Rolls

Shortest Impossible Sequence of Rolls

What is this problem about?

The Shortest Impossible Sequence of Rolls interview question gives you an array of dice rolls where each roll is an integer in [1, k]. Find the length of the shortest sequence of values in [1..k] that is NOT a subsequence of the rolls array. For example, if k=2 and rolls = [1,2,1], the answer is 3 because all sequences of length 1 ("1","2") and length 2 ("1,1","1,2","2,1","2,2") are subsequences, but some length-3 sequence is not.

Why is this asked in interviews?

Google asks this HARD problem because it requires a greedy insight about subsequence coverage. To have every sequence of length L as a subsequence of rolls, you need to be able to find all k distinct values at least L times in order. The greedy approach: count how many complete sets of all k values you can find as disjoint subsequences in rolls. The answer is (number of complete sets + 1).

Algorithmic pattern used

The pattern is greedy with a sliding window over complete sets. Maintain a set of "values seen so far" in the current round. Scan through rolls: add each value to the current set. When the set contains all k values (a complete round), increment the round counter and reset the set. At the end, the shortest impossible sequence has length round_count + 1. This is O(n) time and O(k) space.

Example explanation

rolls = [4, 2, 1, 2, 3, 3, 4, 1, 2], k = 4.

Scan to find complete sets {1,2,3,4}:

• Round 1: accumulate until {1,2,3,4} found → positions 0-4 complete. Round count=1. Reset.
• Round 2: continue from position 5: 3,4,1,2 → complete! Round count=2. Reset.
• No more values → stop.

Shortest impossible sequence length = 2+1 = 3.

(Every sequence of length 1 and 2 is a subsequence; some sequence of length 3 is not.)

Common mistakes candidates make

• Confusing "subsequence" with "substring" — subsequences don't need to be contiguous.
• Using a frequency count instead of a set — within each round, each value only needs to appear once (it's a set problem, not a frequency problem).
• Off-by-one in the answer — the answer is (complete rounds + 1), not just complete rounds.
• Using O(k × n) scan for each round instead of the single-pass greedy.

Interview preparation tip

For the Shortest Impossible Sequence of Rolls coding problem, the hash table greedy interview pattern is the elegant O(n) approach. The key insight: each "round" where all k values appear forms one layer of coverage. After r complete rounds, all sequences of length ≤ r are guaranteed subsequences, but some length-r+1 sequence is not. Google interviewers value the precise explanation of why the answer is r+1. Practice explaining the greedy invariant before coding — this problem rewards mathematical clarity over implementation complexity.