← JPMorgan Chase Interview Insights

JPMorgan Chase·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Interviewed for a Quant Engineer role at JP Morgan. The technical portion had a classic combinatorics/DP problem that looks simple on the surface but trips you up if you haven't seen the pattern before.

Questions Asked (1)

Q1

Given a 2×N rectangle, how many distinct ways can you tile it completely using 1×2 and 2×1 dominoes?

Algorithms & Data Structures
Author's notes

I knew this was a DP problem pretty fast but fumbled explaining the recurrence cleanly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

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.

1. Define the problem and base cases

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).

2. Derive recurrence relation

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).

3. Identify sequence and optimize

Recognize the recurrence generates Fibonacci numbers. Compute iteratively from base cases, using only two variables to achieve O(1) space.

4. Implement and test

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.

Key Points to Mention

  • Dynamic programming approach with overlapping subproblems
  • Recurrence relation: f(n) = f(n-1) + f(n-2)
  • Base cases: f(0)=1, f(1)=1
  • Fibonacci sequence connection
  • Time complexity O(n) and space complexity O(1) with iterative optimization
  • Edge cases: n=0, n=1, and large n (potential integer overflow)

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.