Katkat
Back

Find the Two Heaviest Balls with Minimum Comparisons

Point72Quantitative Researcher · Technical Screen
HardQuantitative ResearcherTechnical ScreenStatistics & Math

Last updated

There are 32 balls with distinct weights. Explain the assumptions and derivation clearly, check edge cases, and show how the result changes when those assumptions no longer hold.

Find the Two Heaviest Balls with Minimum Comparisons

There are 32 balls with distinct weights. A comparison reveals which of two balls is heavier. Determine the minimum number of comparisons needed to identify both the heaviest and second-heaviest balls, give an algorithm that achieves it, and prove that fewer comparisons cannot always succeed.

Constraints & Assumptions

  • All weights are distinct.
  • Only pairwise comparisons are allowed.
  • The algorithm may choose later comparisons based on earlier outcomes.
  • Both identities, not their numeric weights, must be returned.

Clarifying Questions to Ask

  • Are comparisons deterministic and error-free?
  • Must the lower bound apply to every adaptive comparison strategy?
  • How should the argument generalize when the item count is not a power of two?

Hints

Hint 1

Preserve comparison evidence: For every ball excluded from either returned position, be able to point to observed comparison outcomes that justify the exclusion.

Hint 2

Separate construction from lower bound: An algorithm that achieves a count does not by itself prove that every adaptive strategy needs that many comparisons.

Follow-up questions

  • What is the comparison count for n balls when n is a power of two?
  • How would the algorithm track the third-heaviest ball?