How should I practice Expected Fake-Name Collisions?

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

Is Expected Fake-Name Collisions associated with Mercor?

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

Expected Fake-Name Collisions

Mercor● EasyFULLTIMEPHONE SCREEN

Problem statement

A pipeline anonymizes a dataset by replacing every real name with a fake name. Each real name always gets the same fake name.

There is a list of fakeNames fake names. For each of the n distinct real names, the pipeline picks one fake name uniformly at random from the list. It does not check whether that fake name was already used, and the picks are independent.

A collision is any pair of real names that end up with the same fake name. For example, three real names that share one fake name form 3 collisions.

Return the expected number of collisions as a reduced fraction string "numerator/denominator" with no spaces. Write a whole number x as "x/1".

Function

expectedCollisions(n: int, fakeNames: int) → String

Examples

Example 1

n = 2fakeNames = 2return = "1/2"

There is one pair of real names. The second name matches the first name's fake with probability 1/2, so the expected number of collisions is 1/2.

Example 2

n = 1000fakeNames = 1000000return = "999/2000"

There are 1000 * 999 / 2 = 499500 pairs. Each pair collides with probability 1/1000000.

By linearity of expectation, the answer is 499500/1000000 = 999/2000.

Example 3

n = 3fakeNames = 1return = "3/1"

With only one fake name, all three real names share it. Every one of the 3 pairs is a collision.

Constraints

1 <= n <= 10^6
1 <= fakeNames <= 10^9