Tile a Three-Row Board with Dominoes
Updated
Problem statement
A board has 3 rows and n columns. Return the number of ways to cover every cell using 1 × 2 and 2 × 1 dominoes.
Dominoes cannot overlap or extend outside the board. Two tilings differ when at least one domino covers a different pair of cells; rotating or reflecting a tiling does not identify it with another tiling.
For this exercise, assume the empty board has one tiling. Return the exact count without taking a modulus.
Function
countTilings(n: int) → intExamples
Example 1
n = 2return = 3One tiling uses three horizontal dominoes. In each of the other two tilings, a pair of vertical dominoes covers either the top two rows or the bottom two rows, and one horizontal domino covers the remaining row. The total is 3.
Example 2
n = 4return = 11There are 9 tilings with no domino crossing the middle vertical line: choose one of the 3 tilings independently for each 3-by-2 half. Exactly 2 further tilings cross that line, for a total of 11.
Example 3
n = 1return = 0The board has 3 cells, an odd number. Every domino covers 2 cells, so a full tiling is impossible.
Constraints
0 <= n <= 30- The answer fits in a signed 32-bit integer.
More JP Morgan Chase Onsite Interview questions
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU CacheONSITE INTERVIEW · Seen Nov 2026
- Employees Above Average SalaryONSITE INTERVIEW · Seen Sep 2026
- Highest-Earning Employees By DepartmentONSITE INTERVIEW · Seen Sep 2026
- K Largest Integers in Descending OrderONSITE INTERVIEW · Seen Aug 2026
- Two SumONSITE INTERVIEW · Seen Nov 2025
- Intersection of Two ListsONSITE INTERVIEW · Seen Jan 2025
- Maximum Subarray SumONSITE INTERVIEW · Seen Jan 2025
- Fibonacci NumberONSITE INTERVIEW · Seen Nov 2024
- Integrate a Sampled FunctionONSITE INTERVIEW · Seen Nov 2024
Similar questions at other companies
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Integer BreakAmazon · ONSITE INTERVIEW
- Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Count Divisible Power SumsGoodScore · ONSITE INTERVIEW
- Two-Egg DroppingNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
- Every Result of Grouping an ExpressionC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Split a Number into Non-Decreasing GroupsExpedia · OA · ONSITE INTERVIEWExpedia interview questions
- Fibonacci NumberMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Largest Minus Smallest Value of a Parenthesized ExpressionNutanix · ONSITE INTERVIEWNutanix interview questions
JP Morgan Chase interview experiences
- JPMorgan Quant Stats Superdays: 3 Experiences (Part 3 of 3)
- JPMorgan Quant Modeling Superdays: 7 Experiences (Part 2 of 3)
- JPMorgan Quant Intern Superday: 19 Experiences (Part 1 of 3)
- JP Morgan Chase Data and AI Intern Superday: 11 Experiences
- JPMorgan Code for Good India 2024: 6 Experiences (Part 5 of 5)
- JPMorgan Code for Good India: 10 Experiences (Part 4 of 5)