How should I practice Domino and Tromino Tiling?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Domino and Tromino Tiling associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Domino and Tromino Tiling

Learn this problem

● Medium

AmazonFULLTIMEONSITE INTERVIEW

See Amazon hiring insights

Problem statement

You have a board with 2 rows and n columns. Cover every square exactly once using any number of the following tiles:

A 2 x 1 domino, which may be rotated.
An L-shaped tromino made of three unit squares, which may be rotated.

Return the number of distinct complete tilings modulo 10^9 + 7. Two tilings are different when at least one tile covers a different set of squares.

Function

numTilings(n: int) → int

Examples

Example 1

n = 1return = 1

One vertical domino is the only complete tiling.

Example 2

n = 3return = 5

There are three domino-only tilings and two tilings that use a complementary pair of trominoes.

Example 3

n = 5return = 24

The dynamic recurrence counts 24 complete tilings.

Constraints

1 <= n <= 1000.