In this article, we will explore and solve three classic quant interview questions often asked at J.P. Morgan, providing you with step-by-step solutions and detailed explanations of the key concepts involved.

Quant Interview Questions from J.P. Morgan

1. Expectation of min(X, Y) Where X, Y Are Independent and Uniform in [0, 1]

Understanding the Problem

Given two independent random variables \(X\) and \(Y\) uniformly distributed on the interval \([0, 1]\), compute the expected value of their minimum, i.e., find \(\mathbb{E}[\min(X, Y)]\).

Key Concepts

• Uniform Distribution
• Joint Probability Density Function (PDF)
• Expectation of a Function of Random Variables
• Integration over Regions

Detailed Solution

Let’s denote \(Z = \min(X, Y)\). Since \(X\) and \(Y\) are independent and uniformly distributed on \([0,1]\), their joint PDF is:

We want to compute \(\mathbb{E}[Z] = \mathbb{E}[\min(X, Y)]\):

To evaluate this, split the integration domain into two regions: \(x \leq y\) and \(x > y\).

• For \(x \leq y\), \(\min(x, y) = x\)
• For \(x > y\), \(\min(x, y) = y\)

Therefore,

Compute the first integral:

Compute the second integral:

Adding both parts:

Alternative Approach Using CDF

Let’s use the cumulative distribution function (CDF) method.

• The CDF of \(Z = \min(X, Y)\) is:
  \[ F_Z(z) = P(\min(X, Y) \leq z) = 1 - P(X > z \text{ and } Y > z) = 1 - (1-z)^2 \]
• The PDF is:
  \[ f_Z(z) = \frac{d}{dz} F_Z(z) = 2(1-z) \]
• Thus,
  \[ \mathbb{E}[Z] = \int_0^1 z \cdot f_Z(z) dz = \int_0^1 2z(1-z) dz = 2 \int_0^1 z - z^2 dz \] \[ = 2 \left[ \frac{1}{2}z^2 - \frac{1}{3}z^3 \right]_0^1 = 2 \left( \frac{1}{2} - \frac{1}{3} \right) = 2 \cdot \frac{1}{6} = \frac{1}{3} \]

Conclusion

The expected value of \(\min(X, Y)\), where \(X\) and \(Y\) are independent and uniformly distributed on \([0,1]\), is:

2. Minimum Number of Socks to Ensure k Pairs of Socks

Understanding the Problem

Suppose you have a box containing red and black socks (with an unlimited number of each color). Each time you take a sock out, you cannot see its color. What is the minimum number of socks you must take out to guarantee you have at least k pairs of socks (a pair is two socks of the same color)?

Key Concepts

• Pigeonhole Principle
• Worst-Case Analysis
• Combinatorics

Detailed Solution

Let’s break down the problem and generalize it:

• There are two colors: red and black.
• A pair is two socks of the same color.
• Goal: Find the minimum number \(n\) such that, no matter which socks you draw, you always have at least \(k\) pairs of the same color.

Formulating the Problem

Let’s denote:

• Let \(R\) be the number of red socks picked.
• Let \(B\) be the number of black socks picked.
• Total picked: \(n = R + B\)

A pair is formed each time you have two socks of the same color. So, the number of red pairs is \(\left\lfloor \frac{R}{2} \right\rfloor\), and black pairs is \(\left\lfloor \frac{B}{2} \right\rfloor\).

Worst-case Scenario

We are interested in the minimum \(n\) such that, no matter how the colors are distributed, the total number of pairs \(\left\lfloor \frac{R}{2} \right\rfloor + \left\lfloor \frac{B}{2} \right\rfloor \geq k\).

Exploring the Worst-case

The worst-case scenario is when the number of red and black socks are as close as possible but not both even, to minimize the number of pairs.

For any \(n\), let’s define:

• If \(n\) is even: \(n = 2m\), choose \(R = m\), \(B = m\). Number of pairs: \(2 \times \left\lfloor \frac{m}{2} \right\rfloor\).
• If \(n\) is odd: \(n = 2m+1\), choose \(R = m\), \(B = m+1\) or vice versa.

But to minimize the number of pairs, arrange so that the number of singles is maximized.

Let’s try to generalize. Given \(n\) socks, the minimal number of pairs we can guarantee is: \[ \min_{R+B = n} \left( \left\lfloor \frac{R}{2} \right\rfloor + \left\lfloor \frac{B}{2} \right\rfloor \right) \]

But the worst case is when the number of odd socks is maximized, i.e., as close as possible to half and half.

Constructing a Formula

Let’s try small values for \(k\) to find a pattern:

Let’s verify for \(k = 2\):

• Take 5 socks. Worst case: 3 red and 2 black. Number of red pairs: 1, black pairs: 1. Total pairs: 2.
• If only 4 socks: could be 2 red, 2 black. Number of pairs: 1+1 = 2 (still 2 pairs), but with 3 socks: could be 2 red, 1 black. Only 1 pair.

So, the minimal number is \(2k + 1\).

General Formula

To guarantee \(k\) pairs, you need to pick \(2k + 1\) socks.

Explanation

• With \(2k\) socks, the worst case is you have \(k\) red and \(k\) black, forming \(k\) pairs.
• But with only \(2k\) socks, it’s possible to have \(k-1\) pairs (if the distribution is uneven).
• With \(2k + 1\) socks, no matter how they are distributed, you must have at least \(k\) pairs.

Formal Proof

Let’s distribute the \(2k + 1\) socks into red (\(r\)) and black (\(b\)) such that \(r + b = 2k + 1\). The minimal number of pairs is: \[ \left\lfloor \frac{r}{2} \right\rfloor + \left\lfloor \frac{b}{2} \right\rfloor \] To minimize the number of pairs, maximize the number of odd socks, i.e., let both \(r\) and \(b\) be as odd as possible. If \(r\) and \(b\) are both odd, their sum is even, which contradicts \(2k + 1\) being odd. So, one will be even, the other odd. So, the minimal number of pairs is: \[ \left\lfloor \frac{(2k+1) - 1}{2} \right\rfloor + \left\lfloor \frac{1}{2} \right\rfloor = k + 0 = k \]

Conclusion

To guarantee at least \(k\) pairs of socks, you must pick at least \(2k + 1\) socks from the box.

3. Maximum Sum of Subsequence of an Array

Understanding the Problem

Given an array of integers (possibly containing negative numbers), find the maximum sum that can be obtained from a contiguous subsequence (subarray) of the array. This classic problem is often known as the "Maximum Subarray Problem" or "Kadane's Algorithm".

Key Concepts

• Dynamic Programming
• Greedy Algorithms
• Subarray vs Subsequence
• Contiguous Sums

Detailed Solution

Let’s denote the array as \(A = [a_1, a_2, \ldots, a_n]\). We are looking for the maximum sum over all possible contiguous subarrays, i.e., find: \[ \max_{1 \leq i \leq j \leq n} \left( \sum_{k=i}^j a_k \right) \]

Brute Force Approach

A naive solution is to check all possible subarrays, compute their sums, and return the maximum. This approach has time complexity \(O(n^2)\) or \(O(n^3)\).

Kadane’s Algorithm (Efficient Solution)

Kadane’s algorithm solves this problem in \(O(n)\) time. The idea is to iterate through the array, keeping track of the maximum sum ending at the current position, and updating the global maximum.

Algorithm Steps

• Initialize two variables:
  • max_ending_here: maximum sum of subarray ending at current indexmax_so_far: overall maximum sum found so far
• Iterate through the array:
  • At each element a_i, update max_ending_here as the maximum of a_i and max_ending_here + a_i
  • Update max_so_far if max_ending_here exceeds it

Mathematical Formulation

Let’s define recursively for i = 1, ..., n:

Python Implementation

def max_subarray_sum(arr):
    max_ending_here = max_so_far = arr[0]
    for x in arr[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

# Example usage:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # Output: 6

Explanation of the Example

Given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subsequence with the maximum sum is [4, -1, 2, 1], which sums to 6.

Step-by-Step Walkthrough

Complexity Analysis

• Time Complexity: O(n) (single pass through the array)
• Space Complexity: O(1) (constant space)

Handling All-Negative Arrays

Kadane’s algorithm as presented works for arrays with all negative numbers as well, returning the largest (least negative) number.

Extension: Finding the Subarray Itself

To also track the subarray indices, you can slightly modify the algorithm:

def max_subarray_with_indices(arr):
    max_ending_here = max_so_far = arr[0]
    start = end = s = 0
    for i in range(1, len(arr)):
        if arr[i] > max_ending_here + arr[i]:
            max_ending_here = arr[i]
            s = i
        else:
            max_ending_here += arr[i]
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = s
            end = i
    return (max_so_far, start, end)

# Example usage:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_with_indices(arr))  # Output: (6, 3, 6)

This tells us the maximum sum is 6 and the subarray is from index 3 to 6.

Summary Table: J.P. Morgan Quant Interview Questions and Solutions

Conclusion

Quant interviews at J.P. Morgan are designed to test a blend of analytical thinking, mathematical rigor, and algorithmic skills. By practicing problems like the expectation of the minimum of two uniform random variables, combinatorial reasoning with socks and pairs, and efficient algorithms such as Kadane’s for maximum subarray sum, you prepare yourself for a wide range of quant interview scenarios. Understanding these concepts deeply and being able to explain your reasoning clearly will give you a significant edge in your interview process.

Continue to challenge yourself with variations of these problems, and always strive to understand the underlying principles rather than just memorizing solutions. Good luck with your quant interviews!

Related Articles

• Quant Interview Questions from Citadel Securities