← JP Morgan Interview Insights

JP Morgan·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Quant engineer interview at JP Morgan with a combinatorics/dynamic programming problem that felt more like a math olympiad warmup than anything I expected from a finance role. The question had real depth once you got past the setup.

Questions Asked (1)

Q1

How many distinct ways can you tile a 3xN rectangle using 1x2 and 2x1 dominoes? Derive a recurrence relation and generalize to arbitrary N.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I'd seen domino tiling problems before but always on 2xN grids, so the 3xN version threw me more than I expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by analyzing small N to identify patterns, then derive a recurrence relation by considering how the first column can be tiled. Use the recurrence to compute the number of tilings for any N, and discuss the time and space complexity of the solution.

Pro tip: Mention that the recurrence can be solved in O(log N) using matrix exponentiation, which is crucial for large N and demonstrates algorithmic maturity.

1. Understand the problem and define states

Clarify that we need to count distinct tilings of a 3xN grid with 1x2 and 2x1 dominoes. Define a state representation for the boundary between tiled and untiled regions.

2. Analyze small cases and identify patterns

Manually compute the number of tilings for N=1,2,3,4 to see the sequence and guess a recurrence. Note that N must be even for a non-zero count.

3. Derive recurrence relation

Consider the leftmost column and enumerate all possible ways to tile it, leading to a recurrence like f(N) = 4f(N-2) - f(N-4) or similar. Explain the reasoning clearly.

4. Solve and generalize

Solve the recurrence to get a closed form or use matrix exponentiation for efficient computation. Discuss base cases and how to handle arbitrary N.

5. Discuss complexity and trade-offs

Compare iterative DP (O(N) time, O(1) space) with matrix exponentiation (O(log N) time). Mention that for large N, matrix exponentiation is preferred.

Key Points to Mention

  • The number of tilings is zero for odd N.
  • The recurrence relation for 3xN is f(N) = 4f(N-2) - f(N-4) with base cases f(0)=1, f(2)=3.
  • Matrix exponentiation can compute f(N) in O(log N) time.
  • Dynamic programming with O(N) time and O(1) space is sufficient for moderate N.
  • The problem is a classic example of tiling and can be extended to other grid sizes.
  • Explain the derivation by considering the first column and the possible placements of dominoes.

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