← JPMorgan Chase Interview Insights

JPMorgan Chase·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Quant engineer interview at JP Morgan, one technical question that looked like a math puzzle but was really a dynamic programming problem. Not a lot of context given about the round or outcome.

Questions Asked (1)

Q1

How many distinct ways can you tile a 3-by-N rectangle using 1x2 and 2x1 dominoes? Derive a recurrence relation and generalize the count for any N.

Algorithms & Data Structures
Author's notes

This one took me a minute to even parse.

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 the placement of the first domino. Solve the recurrence to get a closed-form or efficient computation, and generalize for any N.

Pro tip: Mention that the recurrence can be computed in O(N) time with O(1) space, and note that for large N, the count grows exponentially, so modulo arithmetic may be needed in practice.

1. Base cases and small N

Compute the number of tilings for N=0,1,2,3,4 manually to identify initial values and patterns.

2. Derive recurrence

Consider the leftmost column: either place a vertical domino (reducing to N-1) or two horizontal dominoes (reducing to N-2). This gives f(N) = f(N-1) + 2*f(N-2) for N>=2, with f(0)=1, f(1)=0.

3. Solve recurrence

Solve the characteristic equation r^2 = r + 2, giving roots r=2 and r=-1. Use initial conditions to find constants, yielding f(N) = (2^N + 2*(-1)^N)/3 for even N, and 0 for odd N.

4. Generalize and discuss

State the closed-form for any N, and discuss time/space complexity of computing it iteratively. Mention that for odd N, the answer is 0.

Key Points to Mention

  • Base cases: f(0)=1, f(1)=0, f(2)=3, f(3)=0, f(4)=11
  • Recurrence relation: f(N) = f(N-1) + 2*f(N-2) for N>=2
  • Closed-form: f(N) = (2^N + 2*(-1)^N)/3 for even N, 0 for odd N
  • Time complexity: O(N) iterative, O(log N) with matrix exponentiation
  • Space complexity: O(1) with iterative approach
  • Modulo arithmetic for large N to avoid overflow

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