← JPMorgan Chase Interview Insights
I knew this was a DP problem pretty fast but fumbled explaining the recurrence cleanly.
Recognize this as a classic dynamic programming problem where the number of tilings follows a Fibonacci sequence. Derive the recurrence relation f(n) = f(n-1) + f(n-2) by considering the last column's placement, then implement an iterative solution with O(N) time and O(1) space.
Pro tip: Mention that this is equivalent to the Fibonacci sequence and discuss how you would optimize space by only keeping the last two values, showing awareness of both time and space complexity.
Let f(n) be the number of ways to tile a 2×n rectangle. Establish base cases: f(0)=1 (empty tiling), f(1)=1 (one vertical domino).
Consider the last column: it can be filled by one vertical domino (leaving 2×(n-1)) or two horizontal dominoes (leaving 2×(n-2)). Thus f(n) = f(n-1) + f(n-2).
Recognize the recurrence generates Fibonacci numbers. Compute iteratively from base cases, using only two variables to achieve O(1) space.
Write a function that returns f(n) for a given n, handling edge cases (n=0,1). Test with small n to verify: f(2)=2, f(3)=3, f(4)=5.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.