Secretary Problem – Selecting the Most Valuable Painting
Quick Overview
Practice an optimal stopping interview problem about choosing one painting from 100 rooms. The solution separates expected-value maximization from the classic secretary problem, deriving reservation thresholds for known value distributions and explaining the 37 percent sample-then-select rule for picking the single best painting.
Secretary Problem – Selecting the Most Valuable Painting
Company: TikTok
Role: Product Manager
Category: Product / Decision Making
Difficulty: medium
Interview Round: Onsite
##### Question
A philanthropist invites you to an island with 100 rooms, each containing one painting. You may enter the rooms one at a time in any order, but you cannot return to previous rooms. You may take at most one painting and must decide immediately upon seeing it.
What strategy maximizes the expected value of the painting you take?
How does the strategy change if you receive nothing unless you pick the single most valuable painting?
Quick Answer: Practice an optimal stopping interview problem about choosing one painting from 100 rooms. The solution separates expected-value maximization from the classic secretary problem, deriving reservation thresholds for known value distributions and explaining the 37 percent sample-then-select rule for picking the single best painting.
Secretary Problem – Selecting the Most Valuable Painting
TikTok
Jul 4, 2025, 8:28 PM
mediumProduct ManagerOnsiteProduct / Decision Making
12
0
Optimal Stopping Prompt: Choosing a Painting from 100 Rooms
You are invited to an island with 100 rooms, each containing one painting. You may enter the rooms one at a time in any order, but you cannot return to previous rooms. After seeing a painting, you must immediately decide whether to take it. You may take at most one painting.
Assume you can judge a painting's value when you see it, and the room order is effectively random.
Constraints & Assumptions
Distinguish between maximizing expected value and maximizing the probability of choosing the single best painting.
For expected value, state what distributional information is needed to compute exact thresholds.
For the best-only version, use the classic secretary problem logic.
Explain the strategy in interview-friendly terms before giving formulas.
Clarifying Questions to Ask Guidance
Do we know the distribution of painting values, or only their relative ranks as we observe them?
Is the objective to maximize expected dollar value or only to pick the absolute best painting?
Are painting values independent draws from a distribution?
Do we receive zero if we never select a painting?
Part 1 - Maximize Expected Value
What strategy maximizes the expected value of the painting you take?
What This Part Should Cover Guidance
Dynamic reservation-value strategy.
Accept a painting if its observed value exceeds the expected value of continuing.
Recurrence for known value distribution.
Explanation that exact thresholds require a value distribution or empirical estimate.
Example with a simple distribution, such as Uniform[0,1], if helpful.
Part 2 - Pick the Single Best Painting
How does the strategy change if you receive nothing unless you pick the single most valuable painting?
What This Part Should Cover Guidance
Classic secretary problem.
Sample roughly the first 37% of rooms without selecting.
Record the best value seen during the sample.
Then pick the first later painting that beats the sample best.
If none beats it, take the final painting or accept the risk of no success depending on rules.
What a Strong Answer Covers Guidance
A strong answer explains that expected-value maximization uses value thresholds, while best-only selection uses rank-based sampling. It should not blindly apply the 37% rule to the expected-value version unless the objective is explicitly to select the single best item.
Follow-up Questions Guidance
What if painting values follow a known Uniform[0,1] distribution?
What if you only know relative ranks, not cardinal values?
What changes if you can choose up to two paintings?
What if you are allowed to return to one previous room?
Why is the 37% rule not always optimal for expected value?