Quantitative Researcher

Frog and ChatGPT

Today I tried to solve pre-interview online puzzle solving test by The Susquehanna. A quant recruiter reached out to me on Linkedin asking if I’m interested in internship, I said that I’m currently looking for full-time positions only and he forwarded my CV to another recruiter from SIG. They sent me an email saying that I should complete The Susquehanna Problem Solving Assessment.

I’ve decided to spend some time preparing for the test and asked ChatGPT-4o

Give me an example of technical interview questions at SIG for Quantitative Research.

ChatGPT replied:

At Susquehanna International Group (SIG), quantitative research interviews often focus on probability, statistics, and logical reasoning. Candidates have reported encountering questions such as:

• Probability Puzzles: For example, “A frog is located at point A (0,0) and must reach point B (5,4) by moving one unit up or one unit right, without taking three consecutive steps in the same direction. How many distinct paths can the frog take?” Source: WALL STREET OASIS
• Expected Value Calculations: Questions involving games with cards, dice, or coins, where you’re asked to compute expected values under various scenarios.

I’ve decided to solve the problem about the frog. I’ve spent half an hour, but was only able to count number of possible paths when there are no constraints on how many steps in the same direction frog can take. Imagine how surprised I was that exactly the same question was the last question on the ‘Problem Solving Assessment’ I took later. Even though I’ve already spent some time thinking about the frog question prior to the test, I still couldn’t solve it in allowed time 😅. To be honest, even now, spending hours thinking about this problem I still don’t see how I was supposed to solve it in less than 10 minutes…

Lessons

• ChatGPT is able to give good mock–interview questions.
• I should spend more time preparing for interviews solving different problems I can find online.
• Some problems are harder than they look, prioritize easy problems when time is limited.

Question about Frog

First idea that comes to mind when solving this problem is to first forget about the constraint and find number of all possible paths. Let’s denote \(m=5\) and \(n=4\). Each path is equivalent to string 001011110 where 0 stands for move RIGHT and 1 stands for move UP. There are \((m+n)!\) permutations of a string of length \(m+n\) when all entries are unique. But we should not count the ones that are given by permuting 0 with 0 and 1 with 1. Hence total number of paths is given by binomial coefficient.

Turns out that this calculation did not help us get closer to the final answer❗ One may think that it could be easier to find number of invalid (prohibited) paths and the subtract it from \(126\), but it’s very hard to do because it’s hard not to run into some sort of double counting when dealing with bundled 00 and single 0. In fact, solution is not very straightforward…

I’ve found this thread that contains several analytic solutions, all of which seem very cumbersome and some require knowledge about combinatorics that I do not possess. Given that in our case \(m=5\) and \(n=4\) are relatively small numbers we can adopt the solution that uses partitions.

The idea is that final path is made by combining one of the partitions of 4 with one of the partitions of 5, of course, only particitions with similar lengths could be matched, so there $5$ options. If partitions have the same length, that either 0 or 1 can go first, so there is an additional factor of \(2\). Let’s denote multiplicity factor for partition of \(n\) of length \(k\) as \(P^{[n]}_k\), then answer is

This is in fact the right answer.

Checking the answer with Python

Finally, one could tackle this problem with brute-force.

import numpy as np

def generate_paths(m: int, n: int) -> np.ndarray:
    """
        Function to generate all possible paths from (0,0) to (m,n).
        Only two moves are allowed: right and up.
    """
    if m == 0 and n == 0:
        return np.array([[]])
    if m == 0:
        return np.array([[1]*n])
    if n == 0:
        return np.array([[0]*m])

    paths = np.empty((0, m + n))
    for path in generate_paths(m - 1, n):
        paths = np.append(paths, np.append(path, 0).reshape(1, m + n), axis=0)
    for path in generate_paths(m, n - 1):
        paths = np.append(paths, np.append(path, 1).reshape(1, m + n), axis=0)

    return paths

def isvalid(path: np.ndarray, k_max: int = 2) -> bool:
    """
        If path contains more then k_max consecutive moves in the same direction,
        return False. Otherwise return True.
    """
    k = 1
    for i in range(1, len(path)):
        if path[i] == path[i-1]:
            k += 1
        else:
            k = 1
        if k > k_max:
            return False
    return True

Result of the code above is summarized in the following animation created with frog.py

Interview Questions

Problems: Download PDF Solutions: Download PDF