How should I practice Expected City Arrival and Return Days?

Start by reading the full statement, solve the visible examples, then compare the pattern against related IMC Trading phone screen problems in FastPrep.

Is Expected City Arrival and Return Days associated with IMC Trading?

FastPrep tags this as a IMC Trading phone screen coding practice problem when the problem catalog has that company and stage context.

Expected City Arrival and Return Days

IMC Trading● MediumFULLTIMENEW GRADPHONE SCREEN

Learn

Problem statement

A traveler moves among cities once per day according to the probabilities represented by transitionWeights. Return one expected number of days for every starting city.

For a starting city different from target, count days until the first visit to the target, then stop.

For this exercise, assume a traveler starting in the target on day zero makes at least one normal daily transition. Count days until their first return to the target at a positive time. Staying there on day one counts as return after one day. Leaving is allowed but is not forced. This makes the author clarification about day-zero departure precise.

For this exercise, assume the city count, row weights and target index are parameters, with positive off-diagonal weights so expectations are finite. Complete expectedCityArrivalDays(transitionWeights,target). For each entry, an answer is accepted when its absolute error is at most 1e-7 * max(1, abs(expected)), using a relative-or-absolute tolerance of 1e-7.

Function

expectedCityArrivalDays(transitionWeights: int[][], target: int) → double[]

Examples

Example 1

transitionWeights = [[2,1,1],[1,0,1],[1,1,2]]target = 0return = [2.5,2.6666666666666665,3.3333333333333335]

In NYC, Nashville, SF order, the reported probabilities give [5/2,8/3,10/3]. The non-target equations are H_N=1+H_S/2 and H_S=1+H_N/4+H_S/2. Starting at NYC, positive-time return is 1+H_N/4+H_S/4=5/2.

Example 2

transitionWeights = [[1]]target = 0return = [1.0]

The only city is reached again on day one, so positive-time return takes one day.

Example 3

transitionWeights = [[0,1],[1,0]]target = 0return = [2.0,1.0]

City one reaches the target after one day. Starting at target city zero leaves for city one and returns after two days.

Example 4

transitionWeights = [[0,3],[1,2]]target = 0return = [4.0,3.0]

From city one, each day reaches city zero with probability one third, giving expected hitting time three. Starting at city zero first takes one day to city one, then three expected days to return.

Constraints

For this exercise, assume a square matrix of 1 <= n <= 10 cities, with integer weights from 0 through 100.
For n>1, every off-diagonal weight is at least one; diagonal weights may be zero. For one city, its sole weight is positive.
Each row is normalized independently: P[i][j]=transitionWeights[i][j]/sum(transitionWeights[i]).
For this exercise, assume outputs follow input city order and inputs are not modified.
0 <= target < n.