Domino and Tromino Tiling

Domino and Tromino Tiling

What is this problem about?

The Domino and Tromino Tiling coding problem asks you to find the number of ways to tile a 2 x n board using two types of tiles: 2x1 dominos and L-shaped trominos. The tiles can be rotated. Since the number of ways can be very large, you need to return the answer modulo 10^9 + 7. This is a more complex version of the standard Fibonacci tiling problem.

Why is this asked in interviews?

Companies like Google and Meta ask the Domino and Tromino Tiling interview question to evaluate a candidate's mastery of dynamic programming interview pattern. It requires identifying multiple states (e.g., a fully filled column vs. a partially filled column) and deriving the transitions between them. It tests your ability to handle complex recurrence relations and optimize them for space.

Algorithmic pattern used

This is a Dynamic Programming problem. We define states based on the configuration of the board at width i.

• dp[i][0]: The number of ways to completely fill a 2x(i) board.
• dp[i][1]: The number of ways to fill a 2x(i) board with one extra square in the top row of column i+1.
• dp[i][2]: The number of ways to fill a 2x(i) board with one extra square in the bottom row of column i+1. By symmetry, dp[i][1] and dp[i][2] are often equal. The recurrence involves combining these states using various tile placements.

Example explanation

For n = 3:

1. We can use three vertical dominos.
2. We can use one vertical and two horizontal dominos (two ways: vertical on left or vertical on right).
3. We can use two trominos (two ways: they interlock to fill the 2x3 space). Total ways for n=3 is 5. As n increases, the interdependencies between "completely filled" and "partially filled" states grow, leading to the recursive formula.

Common mistakes candidates make

• Missing States: Forgetting to account for the "protruding" states that trominos create, which are essential for the recurrence.
• Modulo Errors: Not applying the modulo operator at every addition, leading to overflow before the final result.
• Incorrect Base Cases: Miscalculating the number of ways for n=1 or n=2, which cascades into wrong answers for all subsequent values.

Interview preparation tip

When solving tiling problems, draw the possible ways to fill the "last" column. This visual approach helps identify all possible transitions from previous states (i-1, i-2, etc.) and ensures no configurations are missed.