Optimize invites under capacity constraints
Company: Capital One
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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:
1) 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.)
2) 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.
3) Explain how you'd incorporate uncertainty in p and a (e.g., prediction intervals) to produce a risk-aware selection.
Quick Answer: 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.
A nonprofit can reach each of `n` donors either by **email (online)** or by **inviting them to a gala**, but not both. For each donor `i` you are given four parallel arrays: `p_online[i]` (probability of donating if emailed), `a_online[i]` (expected gift amount conditional on donating online), `p_gala[i]`, and `a_gala[i]` (the gala analogues). There are per-person costs `c_online` (per emailed donor) and `c_gala` (per gala attendee), plus a one-time gala fixed cost `F_gala`. You may email everyone, but the gala venue holds at most `K` donors, so you may invite at most `K` donors to the gala.
Let the gala be held regardless (so `F_gala` is always paid). Choose a set `G` with `|G| <= K` to maximize the expected total net revenue:
sum_{i in G} (p_gala[i]*a_gala[i] - c_gala)
+ sum_{i not in G} (p_online[i]*a_online[i] - c_online)
- F_gala
Return the maximum achievable expected total net revenue, rounded to 6 decimal places.
**Approach (O(n log n)):** Start from the baseline where every donor is emailed: `base = sum_i (p_online[i]*a_online[i] - c_online) - F_gala`. Moving donor `i` from email to the gala changes the objective by `delta_i = (p_gala[i]*a_gala[i] - c_gala) - (p_online[i]*a_online[i] - c_online)`. Because the only constraint is the count `|G| <= K`, the moves are independent: greedily apply the moves with the largest positive `delta_i`, up to `K` of them, stopping once `delta_i <= 0`. Sorting the deltas dominates at O(n log n).
Constraints
- 0 <= n <= 100000
- All four probability/amount arrays have the same length n
- 0 <= p_online[i], p_gala[i] <= 1
- a_online[i], a_gala[i] >= 0
- 0 <= K (gala capacity); typically K = 100
- c_online, c_gala, F_gala >= 0
- The gala fixed cost F_gala is always paid (the gala is held regardless of |G|)
Examples
Input: ([0.5], [100], [0.8], [1000], 1.0, 100.0, 20000.0, 100)
Expected Output: -19300.0
Explanation: One donor. Online value = 0.5*100 - 1 = 49. Gala value = 0.8*1000 - 100 = 700, so delta = 651 > 0 and the donor is moved to the gala. base = 49 - 20000 = -19951; total = -19951 + 651 = -19300. The large fixed cost dominates.
Input: ([0.1, 0.1, 0.1], [10, 10, 10], [0.9, 0.9, 0.9], [1000, 1000, 1000], 1.0, 100.0, 0.0, 2)
Expected Output: 1600.0
Explanation: Each online value = 0.1*10 - 1 = 0; each gala value = 0.9*1000 - 100 = 800, so delta = 800. K = 2 caps the gala at two donors. base = 0; total = 0 + 800 + 800 = 1600. The third donor stays online despite a positive delta because of the capacity limit.
Hints
- Rank donors by Delta_i = (p_gala[i]*a_gala[i] - c_gala) - (p_online[i]*a_online[i] - c_online): this is the marginal gain of moving donor i from email to the gala.
- Since the only constraint is the count |G| <= K, the moves are independent — there is no interaction between donors — so a greedy pick of the top-K positive deltas is optimal.
- Compute the all-online baseline first (sum of online values minus F_gala), then add only the positive deltas among the top K. Never take a delta <= 0.
- Sorting the deltas is the O(n log n) bottleneck; you could also use a partial selection (e.g. a size-K heap) for O(n log K).