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.

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.

How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Capital One.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Capital One during technical interviews.

Optimize invites under capacity constraints | Capital One Interview Question

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.

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.

Optimize invites under capacity constraints

Quick Overview

Comments (0)

Optimize invites under capacity constraints

Quick Overview

Comments (0)