n-k nightmare

What this order-statistics interview question tests

This is a medium-difficulty probability question that appears frequently in quant interviews. It asks you to find the expected value of the maximum element in a random sample drawn without replacement from a finite set. The question rewards clean reasoning about order statistics over brute-force enumeration.

To solve problems like this, candidates typically use symmetry arguments or derive the distribution of the maximum directly. A key insight is recognizing that when you draw k distinct numbers from a uniform set, the maximum is not uniformly distributed—it skews toward larger values. The answer requires you to set up the cumulative distribution function (CDF) or probability mass function (PMF) of the maximum and integrate (or sum) to find its expectation.

• Order statistics and their distributions
• Symmetry arguments in discrete probability
• Sampling without replacement vs. with replacement
• Computing expectations from first principles