In this article, we will break down three questions from Graviton and Qianxiang Group quant interviews, providing detailed explanations, solutions, and practical code examples. This guide will help you prepare for your next quant interview and deepen your understanding of some core quantitative concepts.

Quant Interview Experience from Graviton

1. Matrix Rank Problem: Maximum Rank of \( A^2 \) for a 100×100 Rank-1 Matrix

Understanding the Problem

The problem is as follows:

• Let \( A \) be a \( 100 \times 100 \) matrix with rank 1.
• What is the maximum possible rank of \( A^2 \)?

Matrix Rank: Key Concepts

Before delving into the solution, let’s review some key linear algebra concepts:

• Rank of a Matrix: The rank of a matrix \( A \), denoted \( \text{rank}(A) \), is the maximum number of linearly independent rows or columns in the matrix.
• Product of Matrices: For two matrices \( A \) and \( B \), \( \text{rank}(AB) \leq \min(\text{rank}(A), \text{rank}(B)) \).
• Square of a Matrix: \( A^2 = A \cdot A \).

Solution: Step-by-Step

Step 1: Structure of a Rank-1 Matrix

A rank 1 matrix \( A \) can always be written as the outer product of two non-zero vectors:

\( A = \mathbf{u} \mathbf{v}^T \)

Where \( \mathbf{u} \) and \( \mathbf{v} \) are column vectors in \( \mathbb{R}^{100} \).

Step 2: Squaring the Matrix

Let’s compute \( A^2 \):

\( A^2 = ( \mathbf{u} \mathbf{v}^T ) ( \mathbf{u} \mathbf{v}^T ) = \mathbf{u} ( \mathbf{v}^T \mathbf{u} ) \mathbf{v}^T \)

Notice that \( \mathbf{v}^T \mathbf{u} \) is a scalar (the dot product of \( \mathbf{u} \) and \( \mathbf{v} \)). Therefore,

\( A^2 = ( \mathbf{v}^T \mathbf{u} ) \mathbf{u} \mathbf{v}^T \)

Step 3: Rank of \( A^2 \)

The matrix \( \mathbf{u} \mathbf{v}^T \) is again an outer product, which always has rank 1 (unless one of the vectors is zero, which is not the case here). Hence, \( A^2 \) is a scalar multiple of \( A \), and therefore:

\( \text{rank}(A^2) = 1 \)

The maximum possible rank of \( A^2 \) is 1.

Step 4: Special Case – When \( \mathbf{v}^T \mathbf{u} = 0 \)

If \( \mathbf{v}^T \mathbf{u} = 0 \), then \( A^2 = 0 \) (the zero matrix), whose rank is 0.

• Therefore, the possible ranks of \( A^2 \) are 0 or 1.

Conclusion

The maximum possible rank of \( A^2 \), when \( A \) is a \( 100 \times 100 \) rank-1 matrix, is 1.

2. Rolling Quantile Calculation for a Python DataFrame Using Pandas and Numpy

Problem Statement

Given a DataFrame, how can you calculate the rolling quantile (for example, the rolling 90th percentile) using pandas and numpy?

Rolling Quantile: Definition

A rolling quantile is a statistical measure that computes the quantile (e.g., median, 90th percentile) over a rolling window of observations in a time series or sequence. It is widely used in quantitative finance to understand local distributions and detect outliers or regime changes.

Step-by-Step Solution

Step 1: Sample DataFrame

import pandas as pd
import numpy as np

# Generate a sample DataFrame
np.random.seed(0)
df = pd.DataFrame({'price': np.random.randn(20).cumsum()})
print(df.head())

Step 2: Using Pandas' rolling().quantile() Method

Pandas provides a built-in method to calculate rolling quantiles:

# Calculate rolling 90th percentile with a window of 5
df['rolling_90th'] = df['price'].rolling(window=5).quantile(0.9)
print(df)

Step 3: Custom Implementation Using Numpy (For Multi-Column or Custom Functions)

You can use rolling().apply() with a lambda function that uses numpy.quantile:

# Using numpy's quantile function
quantile_value = 0.9
window_size = 5

df['rolling_90th_np'] = df['price'].rolling(window=window_size).apply(
    lambda x: np.quantile(x, quantile_value)
)
print(df)

Step 4: Rolling Quantile for Multiple Columns

Suppose you have multiple columns and want to calculate rolling quantiles for each:

# Create a DataFrame with multiple columns
df_multi = pd.DataFrame({
    'a': np.random.randn(20),
    'b': np.random.randn(20)
})

# Calculate rolling 75th percentile for all columns
quantile = 0.75
window = 4

df_multi_rolling = df_multi.rolling(window=window).quantile(quantile)
print(df_multi_rolling)

Step 5: Handling NaNs

By default, rolling windows will produce NaNs for the initial periods where the window is not full. You can adjust this with the min_periods argument:

# Rolling quantile with minimum periods
df['rolling_90th_min3'] = df['price'].rolling(window=5, min_periods=3).quantile(0.9)
print(df)

Summary Table: Pandas Rolling Quantile Methods

Additional Tips

• For performance-sensitive applications, use pandas built-ins, as they are optimized.
• Use min_periods to control the minimum number of observations in the window required to return a result.
• For large datasets, consider using dask or numba for parallelized rolling computations.

3. Coin Bag Problem: Divide 1000 Coins into 10 Bags for All Sums (Qianxiang Group)

Problem Statement

A dealer has 1000 coins and 10 bags. He must divide the coins among the 10 bags so that he can make any number of coins (from 1 to 1000) by handing over a few bags (without opening them). How should he divide the coins into the bags?

Key Insights

• The dealer must be able to achieve any integer sum from 1 to 1000 by selecting some subset of the bags.
• Bags cannot be split, and coins in each bag are fixed.

Step-by-Step Solution

Step 1: Formulate the Problem Mathematically

Let the number of coins in the bags be \( b_1, b_2, ..., b_{10} \), with \( b_i \geq 1 \).

For every integer \( k \) (where \( 1 \leq k \leq 1000 \)), there must exist a subset \( S \subseteq \{1,2, ..., 10\} \) such that:

\( \sum_{i \in S} b_i = k \)

Step 2: Binary Representation Insight

This is a classic problem in combinatorics. The optimal solution uses the binary representation of numbers.

• Each bag corresponds to a binary digit (bit).
• The coins in each bag are a power of 2.
• By selecting different combinations of bags, you can form all sums from 1 up to the sum of all coins.

Step 3: Assign Coins as Powers of 2

Let:

• Bag 1: \( 2^0 = 1 \) coin
• Bag 2: \( 2^1 = 2 \) coins
• Bag 3: \( 2^2 = 4 \) coins
• ...
• Bag 10: \( 2^9 = 512 \) coins

Sum of coins:

\( 2^0 + 2^1 + 2^2 + \ldots + 2^9 = 2^{10} - 1 = 1023 \)

But we have only 1000 coins, not 1023.

Step 4: Adjust for 1000 Coins

We need to distribute the bags so that their total is 1000, but still allow for any sum from 1 to 1000.

Let’s try assigning the largest possible powers of 2, and put the “remainder” in the last bag.

• Bag 1: \( 1 \) coin
• Bag 2: \( 2 \) coins
• Bag 3: \( 4 \) coins
• Bag 4: \( 8 \) coins
• Bag 5: \( 16 \) coins
• Bag 6: \( 32 \) coins
• Bag 7: \( 64 \) coins
• Bag 8: \( 128 \) coins
• Bag 9: \( 256 \) coins
• Bag 10: \( x \) coins

Sum of first 9 bags:

\( 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 = 511 \)

So, Bag 10 gets:

\( x = 1000 - 511 = 489 \)

Step 5: Can All Sums from 1 to 1000 Be Achieved?

Let’s analyze if every sum from 1 to 1000 can be formed:

• By using the first 9 bags, we can form any sum from 0 to 511.
• By adding Bag 10 (489 coins), we can form sums from 489 to 511 + 489 = 1000.
• For every \( k \) in \( 512 \) to \( 1000 \), write \( k = 489 + m \), where \( m \) ranges from 23 to 511.

Thus, every sum can be formed.

Step 6: Generalization

For any number \( N \) and \( n \) bags, assign powers of 2 to the first \( n-1 \) bags, and the remainder to the last bag.

\( b_i = 2^{i-1} \) for \( i = 1 \) to \( n-1 \)

\( b_n = N - (2^{n-1} - 1) \)

Final Distribution for 1000 Coins and 10 Bags

Explanation: Why This Works

The key reason this solution works lies in the properties of binary numbers. Any integer between 1 and 511 can be formed by selecting various combinations of the first nine bags, since these correspond to all possible sums of the first nine powers of two (each one included or excluded, just like binary digits set to 0 or 1).

For sums greater than 511, you simply add the 489-coin bag (bag 10) to the possible combinations of 0 to 511, covering every total from 489 to 489+511=1000. Thus, every integer total from 1 to 1000 can be achieved by handing over the right selection of bags.

Python Code: Generating the Bag Distribution

def coin_bags(total_coins=1000, num_bags=10):
    powers = [2**i for i in range(num_bags - 1)]
    last_bag = total_coins - sum(powers)
    bags = powers + [last_bag]
    return bags

print(coin_bags())
# Output: [1, 2, 4, 8, 16, 32, 64, 128, 256, 489]

Generalization: Fewer or More Bags

If you have fewer coins or a different number of bags, the same logic applies:

• List the largest powers of 2 that do not exceed the total number of coins.
• The last bag takes the remainder.

For example, for 7 bags and 100 coins:

print(coin_bags(100, 7))
# Output: [1, 2, 4, 8, 16, 32, 37]

Final Thoughts: Interview Takeaways

Let’s summarize the key concepts and strategies behind each of these quant interview questions:

• Matrix Rank Problems: Understand matrix decompositions, rank properties, and how special structures (like rank-1 matrices) behave under operations such as squaring. Often, the algebraic structure reveals the answer in a few lines of reasoning.
• Rolling Statistics in Pandas: Mastery of pandas rolling window operations and familiarity with numpy statistical functions are essential for data manipulation tasks in quant interviews. Knowing both the built-in and custom approaches is valuable.
• Combinatorial Puzzles: Many puzzles can be solved using number theory or binary representation insights. Try to reduce such problems to familiar mathematical constructions, like binary numbers or geometric series.

Additional Resources for Quant Interview Preparation

• Pandas Rolling Documentation
• Numpy Quantile Documentation
• Math StackExchange: Subset Sum and Binary Representation
• Linear Algebra Resources

Conclusion

Quantitative interviews at Graviton and similar firms challenge candidates to apply deep mathematical insights, algorithmic thinking, and coding proficiency. By working through problems like matrix rank manipulations, rolling quantile calculations, and combinatorial puzzles, you not only prepare for interviews but also strengthen your core quantitative toolkit. Keep practicing, explore each topic in depth, and approach problems with both creativity and rigor. Success in quant interviews comes from a blend of theory, practice, and clear communication—skills that will serve you well throughout your quantitative career.

Related Articles

• Graviton Quant Analyst Interview Questions
• Quant Interview Questions from G-Research
• Matrix Questions from Quant Interviews