Katkat
Back

Design a Population-Weighted Random Country Picker

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests your ability to implement a weighted sampling algorithm efficiently and write testable code by decoupling randomness.

Problem Statement

Implement a class CountryPicker that selects a country from a given list such that the probability of selecting a country is directly proportional to its population.

To ensure efficiency for multiple calls, you should precompute the necessary structures in the constructor. Your implementation must allow for deterministic testing by accepting an optional random number generator (or a seed/provider).

Requirements

  1. __init__(self, country_data): Takes a list of tuples (name, population). Precompute the cumulative weights.
  2. pick(self, random_value): Takes a float random_value in the range [0, 1) and returns the name of the country. This simulates the random selection process.

Constraints

  • Number of countries: up to 10^5.
  • Populations: positive integers.
  • Ensure the solution performs the selection in O(log N) time complexity.

Example

# Input
countries = [("USA", 330), ("Canada", 38), ("Mexico", 126)]

# Total population = 494
# Cumulative ranges: 
# USA: [0, 330)
# Canada: [330, 368)
# Mexico: [368, 494)

picker = CountryPicker(countries)
picker.pick(0.5) # Returns "USA" (0.5 * 494 = 247, which falls in [0, 330))
picker.pick(0.8) # Returns "Mexico" (0.8 * 494 = 395.2, which falls in [368, 494))

Edge Cases

  • Single country list.
  • Extremely large population values (ensure no overflow if using a language with fixed-size integers).

Hints

Hint 1

Map each country to a cumulative frequency range where the upper bound is the sum of its population and the populations of all preceding countries.

Hint 2

Store these cumulative sums in a sorted array and use binary search (`bisect_left`) to find the index corresponding to the random value multiplied by the total population.

Hint 3

By passing the random value as an argument to `pick` rather than generating it inside the method, you allow the caller to inject values to verify the selection boundaries.

Follow-up questions

  • How would you handle a scenario where country populations update frequently? Which data structure would you use to maintain efficiency?
  • If you were to store this data in a database, what SQL query would you use to retrieve a single random record weighted by population?
  • How would you modify this design to implement 'weighted sampling without replacement'?