Domino and Tromino Tiling
Asked at Goldman Sachs
Problem
Domino and Tromino Tiling asks how many ways you can tile a 2 x n board using 2x1 dominoes and L-shaped trominoes, modulo 10^9 + 7. It is a DP problem where the challenge is setting up states correctly — the L-shapes create partially filled columns that plain Fibonacci-style tiling does not have.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
With dominoes only, the answer is Fibonacci. Trominoes add tilings where the right edge is jagged, so you need to track more than "fully tiled up to column i".
Two-state DP: full[i] = ways to completely tile the first i columns; part[i] = ways to tile the first i columns plus one extra cell sticking out in column i + 1 (either top or bottom — symmetric, so count one side and double it).
Transitions: full[i] = full[i-1] + full[i-2] + 2 * part[i-2] and part[i] = part[i-1] + full[i-1].
These collapse into the well-known recurrence dp[i] = 2 * dp[i-1] + dp[i-3], with dp[0] = 1, dp[1] = 1, dp[2] = 2.
Check: dp[3] = 2 * 2 + 1 = 5, which matches the five tilings of a 2x3 board.
Optimal Approach
Step 1: Handle small n: dp[0] = 1, dp[1] = 1, dp[2] = 2.
Step 2: For i from 3 to n: dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD.
Step 3: Return dp[n].
Time: O(n). Space: O(1) if you keep only the last three values.
What Trips People Up in Real Interviews
Using Fibonacci. That ignores trominoes entirely.
Stating 2 * dp[i-1] + dp[i-3] with no derivation. Show the full/partial state transitions and then simplify — interviewers want to see where it comes from.
Forgetting the modulo or applying it only at the end, which overflows in fixed-width languages.
Wrong base cases. dp[0] = 1 (the empty tiling) matters for the recurrence.
Solution Code
def numTilings(n):
MOD = 10**9 + 7
dp = [1, 1, 2]
if n < 3:
return dp[n]
for i in range(3, n + 1):
dp.append((2 * dp[i - 1] + dp[i - 3]) % MOD)
return dp[n]Frequently Asked Questions
What is the Domino and Tromino Tiling problem?
Domino and Tromino Tiling asks how many ways you can tile a `2 x n` board using 2x1 dominoes and L-shaped trominoes, modulo `10^9 + 7`. It is a DP problem where the challenge is setting up states correctly — the L-shapes create partially filled columns that plain Fibonacci-style tiling does not have.
How do you solve Domino and Tromino Tiling?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Domino and Tromino Tiling?
Domino and Tromino Tiling is asked at Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Domino and Tromino Tiling?
- Using Fibonacci. That ignores trominoes entirely.
- Stating `2 * dp[i-1] + dp[i-3]` with no derivation. Show the full/partial state transitions and then simplify — interviewers want to see where it comes from.
- Forgetting the modulo or applying it only at the end, which overflows in fixed-width languages.
- Wrong base cases. `dp[0] = 1` (the empty tiling) matters for the recurrence.