Optimize invites under capacity constraints
Overview
This question evaluates a candidate's competency in probabilistic expected-value optimization, algorithmic efficiency for large-scale inputs, and constrained combinatorial selection including grouped all-or-nothing decisions and cost modeling.
You have n donors (n up to 100,000). For each donor i you know: p_online[i] (probability of donating if emailed), a_online[i] (expected donation conditional on donating), p_gala[i], a_gala[i]. Costs: c_online per person emailed, c_gala per gala attendee, plus gala fixed cost F_gala. You may email everyone, but you can invite at most K=100 donors to the gala; a donor cannot both be emailed and invited to the gala. Choose a set G (|G| ≤ K) to maximize expected total net revenue: sum_{i∈G}(p_gala[i]*a_gala[i] - c_gala) + sum_{i∉G}(p_online[i]*a_online[i] - c_online) - F_gala. Tasks:
- Describe an O(n log n) algorithm to choose G. Provide correctness intuition and complexity. (Hint: rank donors by Δi = (p_gala a_gala - c_gala) - (p_online a_online - c_online) and take the top K with positive Δi.)
- Extend your approach if some donors belong to households that must be invited as a group (all-or-nothing) with varying group sizes; state how this becomes a 0/1 knapsack variant and propose an algorithm or approximation suitable for n=1e5.
- Explain how you'd incorporate uncertainty in p and a (e.g., prediction intervals) to produce a risk-aware selection.