Jane Street SWE Quant OA | 1 Crore CTC | 2027 Grad
Summary
I took an online assessment for a software engineering quant role and encountered a tree‑dependency counting problem.
Full Experience
This is the question asked as per my memory of the test :-
A collection contains N uniquely labeled tokens connected by one-way dependency links. The structure is guaranteed to form a rooted directed tree: exactly one token has no incoming link, and every other token has exactly one incoming link. Every link points away from the root.
A valid arrangement is a sequence of all N tokens such that every token appears strictly after the token it depends on.
For each position i = 1, 2, ..., N, determine how many distinct tokens could occupy that position in at least one valid arrangement.
Formally, for every position i, count the number of vertices u for which there exists a valid arrangement A satisfying A[i] = u - Please help me in solving it :)
Interview Questions (1)
Count possible tokens per position in rooted directed tree
A collection contains N uniquely labeled tokens connected by one-way dependency links. The structure is guaranteed to form a rooted directed tree: exactly one token has no incoming link, and every other token has exactly one incoming link. Every link points away from the root.
A valid arrangement is a sequence of all N tokens such that every token appears strictly after the token it depends on.
For each position i = 1, 2, ..., N, determine how many distinct tokens could occupy that position in at least one valid arrangement.
Formally, for every position i, count the number of vertices u for which there exists a valid arrangement A satisfying A[i] = u.