Google Interview Question: Given a set of cities, each w... | Glassdoor

Interview Question

Software Engineer Intern Interview Dublin, Co. Dublin (Ireland)

Given a set of cities, each with a given population, select

  randomly a city with a probability that is proportional to the population.
Tags:
probability, python
Answer

Interview Answer

2 Answers

0

Gave a naive O(1) time O(population) space solution, then created a python generator that implemented what is requested in O(n_cities) worst-case time.

Interview Candidate on Feb 9, 2011
3

int size = 0
int city_range[]

initialization
  for each city i
    city_range[i] = size
    size += population[i]

selection
  generate random integer r ranging from 0 to size
  for i = 0 to n_cities
    if city_range[i] <= r and r < city_range[i] + population[i]
      return city i

Anonymous on Jan 8, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.