Dataloopr

Quantitative research interviews at top firms like Graviton Research are known for their rigorous mathematical puzzles and probability problems. In this article, we’ll dive into two challenging quant interview questions (including one reportedly asked at Graviton Research), solve them step-by-step, and explain all the underlying concepts.

Quant Research Interview Questions from Graviton Research: Solved and Explained

Table of Contents

• 1. Finding a Flag on the Real Line: Algorithmic Solution
• 2. Gaussian Distributions: Calculating \(P(x > 5y)\)
• 3. Key Quant Concepts Explained
• 4. Tips for Quantitative Research Interviews

1. Graviton Research Quant Interview: The Flag on the Real Line

Problem Statement

Suppose you are standing on the real line at 0. You know that there is a flag planted somewhere on the line at an integer coordinate, you just don't know how far and in which direction. Is there an algorithm to find the flag in time which is linearly dependent on the distance of the flag from the origin?

Understanding the Question

Let’s break down the key elements:

• You start at position 0 on the real line.
• There is a flag at an unknown integer position \( n \), which can be positive or negative.
• Your goal: Devise an algorithm that is guaranteed to find the flag, such that the total distance you travel is linearly dependent on \(|n|\) (the absolute value of the flag’s distance from the origin).

Naive Approach and its Flaw

A naive approach would be to walk first in the positive direction (say, step by step) and, if you don’t find the flag after some time, walk back in the negative direction. However, this method can be highly inefficient if the flag is in the opposite direction, as you may travel much more than \(|n|\) units.

The Optimal Search Algorithm: "Exponential Search"

The optimal strategy is an example of an exponential search or "doubling search," commonly used for unbounded search problems. The core idea is to alternate directions and increase the distance you explore with each attempt.

Step-by-Step Algorithm

1. Start at position 0.
2. For \(k = 1, 2, 3, ...\):
   • If \(k\) is odd, walk to position \(+2^k\) and return to 0.
   • If \(k\) is even, walk to position \(-2^k\) and return to 0.
3. At each step, check each integer coordinate as you pass it. If the flag is at that position, you have found it and can stop.

Pseudocode Implementation

def find_flag():
    position = 0
    k = 1
    while True:
        if k % 2 == 1:
            # Odd k: go to +2^k and back
            for i in range(position, 2**k + 1):
                if is_flag_at(i):
                    return i
            for i in range(2**k, position - 1, -1):
                if is_flag_at(i):
                    return i
        else:
            # Even k: go to -2^k and back
            for i in range(position, -2**k - 1, -1):
                if is_flag_at(i):
                    return i
            for i in range(-2**k, position + 1):
                if is_flag_at(i):
                    return i
        k += 1

Why Does This Work?

• Each time, you double your search distance in alternating directions, ensuring you never miss the flag regardless of its position.
• Suppose the flag is at \(n > 0\). After a certain number of steps, say \(k\), \(2^k \geq n\), so you will find the flag on your way to \(+2^k\).
• If \(n < 0\), the same logic applies in the negative direction.

Analysis: Is the Search Linear in \(|n|\)?

Let’s analyze the total distance traveled:

• At each iteration, the walk is \(2 \times 2^k\) units (go and return).
• For the smallest \(k\) such that \(2^k \geq |n|\), the total distance is dominated by the final segment where you reach or pass the flag.
• The cumulative distance is:
  \[ D = 2 \sum_{j=1}^{k} 2^j = 2(2^{k+1} - 2) \]
  Since \(2^k \leq 2|n|\), \(D = O(|n|)\).

Alternative: The "Zig-Zag" (Spiral) Search

Another variant is to search as follows:

• Go to \(+1\), return to 0.
• Go to \(-2\), return to 0.
• Go to \(+4\), return to 0.
• Go to \(-8\), return to 0.
• ... and so on, doubling the distance and alternating the direction.

This is essentially the same as above but flips the order of exploration. The logic and efficiency remain the same.

Key Takeaways

• This search strategy guarantees an O(|n|) bound on the total distance walked before finding the flag, thus satisfying the requirement of linear dependence.
• This is a classic example of using algorithmic techniques (exponential search) to solve real-world search problems efficiently, making it a favorite in quant interviews.

2. G-Research Quant Interview: Probability with Uncorrelated Gaussians

Problem Statement

Given two uncorrelated Gaussian distributions, both with mean 0 and unit variance, what is the probability that \(x > 5y\) ?

Restating the Problem Mathematically

Let \( x \sim N(0, 1) \), \( y \sim N(0, 1) \), and Cov(\(x, y\)) = 0. Find:

\[ P(x > 5y) \]

Step 1: Understanding the Joint Distribution

Since \(x\) and \(y\) are independent standard normal random variables, their joint distribution is: \[ f(x, y) = \frac{1}{2\pi} e^{-\frac{1}{2}(x^2 + y^2)} \]

Step 2: Express the Probability as a Double Integral

We want: \[ P(x > 5y) = \int_{-\infty}^{\infty} \int_{x > 5y} f(x, y) \, dx \, dy \] Or, equivalently: \[ P(x > 5y) = \int_{-\infty}^{\infty} \left( \int_{x=5y}^{\infty} \frac{1}{2\pi} e^{-\frac{1}{2}(x^2 + y^2)} dx \right) dy \]

Step 3: Variable Substitution

Let’s make a substitution to simplify the integration. Define a new variable: \[ z = x - 5y \] So, \(x = z + 5y\), and when \(x > 5y\), \(z > 0\).

We can think in terms of the joint normal distribution of \(x\) and \(y\).

Distribution of \(z = x - 5y\)

• Since \(x\) and \(y\) are independent, the mean of \(z\) is: \[ E[z] = E[x] - 5E[y] = 0 \]
• Variance of \(z\) is: \[ Var(z) = Var(x) + 25 Var(y) = 1 + 25 = 26 \]
• Thus, \(z \sim N(0, 26)\).

Therefore, \[ P(x > 5y) = P(z > 0) = P(N(0, 26) > 0) \]

Step 4: Probability Calculation

Since the normal distribution is symmetric about zero, \[ P(N(0, \sigma^2) > 0) = 0.5 \]

More formally, \[ P(z > 0) = 1 - \Phi(0) \] where \(\Phi\) is the cumulative distribution function (CDF) of \(N(0, 26)\). Since the mean is 0, \[ \Phi(0) = 0.5 \] so \[ P(x > 5y) = 0.5 \]

Sanity Check: Does This Make Sense?

Yes! For any \(k\), if \(x\) and \(y\) are independent \(N(0, 1)\), \(P(x > ky)\) is always 0.5, because the distribution of \(x - ky\) is symmetric about 0.

Generalization

For any real constant \(k\), \[ x - ky \sim N(0, 1 + k^2) \] so \[ P(x > ky) = P(N(0, 1+k^2) > 0) = 0.5 \]

Alternative Solution: Geometric Interpretation

The set \(\{(x, y): x > 5y\}\) divides the plane into two regions by the straight line \(x = 5y\). The probability that the point \((x, y)\) (drawn from the joint standard normal) lies above this line is exactly 0.5 because the joint distribution is symmetric with respect to any line through the origin.

3. Key Quant Concepts Explained

Exponential (Doubling) Search

Exponential search is a general algorithmic technique for searching when the range is unbounded. The idea is to double the search radius at each step, ensuring you cover the target eventually while keeping the cumulative cost proportional to the distance to the target.

• Application: Searching for an unknown item on an infinite list, or, as in this problem, on the number line.
• Complexity: The total work is always within a fixed multiple of the target distance, i.e., linear in \(|n|\).

Properties of Gaussian Distributions

• Linear Combinations: Any linear combination of independent normal random variables is also normal, with mean and variance given by the linearity of expectation and variance.
• Symmetry: If the mean is zero, the probability of being above or below any straight line through the origin is 0.5.

Change of Variables in Probability

Often, complex probability questions can be reduced to simpler ones by an appropriate change of variables. Here, moving from the inequality \(x > 5y\) to \(z = x - 5y > 0\) turns a joint problem into a single-variable normal probability.

Joint and Marginal Distributions

• For independent random variables, the joint density is the product of the marginals.
• Marginalization and conditioning often reduce the dimensionality of the problem.

Standard Normal Cumulative Distribution Function (\(\Phi\))

The CDF of the standard normal is: \[ \Phi(a) = P(Z \leq a) \] where \(Z \sim N(0, 1)\).

4. Tips for Quantitative Research Interviews

1. Practice Algorithmic Thinking

Many quant interview questions test your ability to devise efficient algorithms, not just your knowledge of math. Practice problems that require search strategies, optimizations, and careful analysis of time complexity.

2. Master Probability Transformations

Be comfortable with joint, marginal, and conditional probability, as well as changing variables and integrating over regions defined by inequalities.

3. Know Your Distributions

Understand the properties of Gaussian (normal), exponential, and other key distributions. Many interview problems involve manipulating or combining random variables.

4. Communicate Clearly

def search_flag(is_flag_at):
    pos = 0
    step = 1
    direction = 1
    while True:
        for i in range(pos, pos + direction * step, direction):
            if is_flag_at(i):
                return i
        pos += direction * step
        step *= 2
        direction *= -1