Map Random Tickets to Population-Weighted Cities
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Cities have positive population weights. Convert deterministic random tickets into city selections so that drawing a uniformly random ticket from `1` through total population would select each city in proportion to its population. Return the city selected for every supplied ticket.
### Function Contract
Implement `select_cities(cities, populations, tickets) -> list[str]`. City `i` owns a contiguous ticket range of length `populations[i]` in the given city order.
### Constraints
- `1 <= len(cities) = len(populations) <= 200000`, and city names are unique.
- `1 <= populations[i] <= 10^12`.
- `sum(populations) <= 9007199254740991`, which is `2^53 - 1`.
- Every ticket is an integer in `[1, sum(populations)]`.
- `0 <= len(tickets) <= 200000`.
- All numeric inputs are within the exact cross-language integer range from `-(2^53 - 1)` through `2^53 - 1`.
### Examples
- Cities `["A","B","C"]`, populations `[2,3,1]`, and tickets `[1,2,3,5,6]` return `["A","A","B","B","C"]`.
- With one city, every valid ticket selects that city.
```hint Build cumulative endpoints
Each city owns tickets after the previous cumulative population through its own cumulative population; binary search finds the first endpoint at least as large as a ticket.
```
### Edge Cases
- The total may approach `2^53 - 1` but never exceed it.
- A ticket exactly on a cumulative boundary belongs to that boundary's city.
- Tickets can be unsorted and repeated.
Overview: Map deterministic tickets to cities in proportion to their population weights by building cumulative ranges and locating each possibly repeated ticket efficiently.
Given unique city names, positive population weights, and deterministic ticket numbers, return the city selected by each ticket. In the given city order, city i owns the next contiguous block of tickets whose length is populations[i]. Ticket numbers are one-indexed from 1 through the total population. Tickets may be empty, unsorted, or repeated, and the result must preserve their order.
Constraints
- 1 <= len(cities) = len(populations) <= 200000, and city names are unique.
- 1 <= populations[i] <= 10^12.
- sum(populations) <= 9007199254740991 (2^53 - 1).
- Every ticket is an integer in [1, sum(populations)].
- 0 <= len(tickets) <= 200000.
- All numeric inputs are within the exact cross-language integer range from -(2^53 - 1) through 2^53 - 1.
Examples
Input: (['A', 'B', 'C'], [2, 3, 1], [1, 2, 3, 5, 6])
Expected Output: ['A', 'A', 'B', 'B', 'C']
Explanation: This is the source example and covers both interiors and cumulative boundaries.
Input: (['X'], [10], [1, 5, 10])
Expected Output: ['X', 'X', 'X']
Explanation: Every valid ticket selects the only city.
Hints
- Build cumulative population endpoints in the given city order.
- For each ticket, find the first cumulative endpoint that is at least that ticket.