← JP Morgan Interview Insights

JP Morgan·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Interviewed for a Quant Engineer role at JP Morgan and got hit with a classic combinatorics DP problem. Not a bad experience but also not a particularly revealing one.

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

Knew this one from competitive programming prep so the recurrence clicked fast.

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 ways to tile a 2×N rectangle follows the Fibonacci sequence. Derive the recurrence relation f(n) = f(n-1) + f(n-2) by considering the last column's placement, then implement an efficient solution with O(N) time and O(1) space.

Pro tip: Mention that this is equivalent to the Fibonacci sequence and discuss how to optimize space to O(1) 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: either a vertical domino covers it (leaving 2×(n-1)) or two horizontal dominoes cover the last two columns (leaving 2×(n-2)). Thus f(n) = f(n-1) + f(n-2).

3. Identify sequence and compute

Recognize that this recurrence generates the Fibonacci numbers. Compute f(n) iteratively from base cases to avoid exponential recursion.

4. Optimize space and handle edge cases

Use two variables to store previous values, achieving O(1) space. Handle n=0, n=1, and large n (e.g., modulo if needed).

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
  • Connection to Fibonacci sequence
  • Time complexity O(n) and space complexity O(1) with iterative optimization
  • Potential need for modulo for large n in coding interviews

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