When I first came across the hiring problem, I realized it isn’t really about hiring at all — it’s a teaching device. I use it here to explain two ideas that show up again and again in algorithm design: probabilistic analysis and randomized algorithms. The problem asks a simple question — if I’m interviewing a sequence of candidates one by one and I always hire whoever is better than my current best, how much will this cost me in the worst case, and how much will it cost me on average? The answer turns out to be surprisingly elegant, and it sets up the tools I need for analyzing algorithms whose behavior depends on chance rather than just on input size.
History and Background
The hiring problem as a teaching example comes from Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms (CLRS), one of the most widely used algorithms textbooks in the world. I trace its purpose back to a broader movement in computer science during the 1970s and 1980s, when researchers like Michael Rabin and others began formalizing randomized algorithms as a legitimate area of study — algorithms that use random choices to achieve good expected performance even when worst-case performance might be bad. The hiring problem itself is a simplified, intuitive scaffold built on top of an older statistical idea: the analysis of records in a random sequence, which statisticians had studied long before computer science existed. CLRS repurposed this classic “records” problem into something a beginning algorithms student could relate to immediately — the everyday act of interviewing candidates for a job.
Problem Statement
I need an office assistant, and I’ve hired an employment agency to send me candidates, one per day. I interview a candidate and decide, on the spot, whether to hire them. If I hire someone, I fire whoever I currently have (if anyone) and pay a fee to the agency for finding this better candidate. I never go back and rehire someone I turned away. My rule is simple: I always hire the candidate if they are better than my current hire. The question is — how much does this strategy cost me, both in the worst case and on average, given that candidates arrive in some order I don’t control?
Core Concepts
Before I go further, I want to fix some terminology:
- Candidate ranking: I assume all $n$ candidates can be strictly ranked from best to worst, and I interview them in some order.
- Worst-case analysis: I assume an adversary controls the order in which candidates arrive, and I ask what the worst possible outcome looks like.
- Probabilistic analysis: Instead of assuming an adversarial order, I assume the order is random, and I compute the expected cost, averaged over all possible orderings.
- Indicator random variable: A random variable that takes the value 1 if some event happens and 0 otherwise. This is the main mathematical trick that makes the analysis of the hiring problem tractable.
- Randomized algorithm: An algorithm that makes some of its decisions using random numbers, rather than depending on the input already being in a random order. The hiring problem naturally leads me to this idea, because if I can’t trust that the agency sends candidates in random order, I can randomize the order myself.
How It Works
Here’s the procedure I use, step by step:
- I set my current best hire to “none” and my total hiring cost to zero.
- For each candidate $i$ from 1 to $n$, in the order they arrive:
- I interview candidate $i$, which costs a small interview fee $c_i$.
- If candidate $i$ is better than my current best hire, I hire them, paying a larger hiring fee $c_h$, and update my current best hire to candidate $i$.
- After all $n$ candidates have been interviewed, I stop. My current best hire is my final office assistant.
Working Principle
The internal logic hinges on one observation: I hire a new candidate exactly when that candidate is better than everyone I’ve seen so far. In probability terms, candidate $i$ is hired if and only if candidate $i$ is the best among the first $i$ candidates — this is what’s called a “running maximum” or a “record” in the sequence. In the worst case, an adversary can hand me candidates in increasing order of quality, so I hire every single one — that’s $n$ hires. But if I assume the candidates arrive in a random order (all $n!$ orderings equally likely), the number of times a new record appears is much smaller on average, because it becomes increasingly unlikely that a late-arriving candidate beats everyone before them.
Mathematical Foundation
Let me define an indicator random variable $X_i$ for each candidate $i$:
$$ X_i = \begin{cases} 1 & \text{if candidate } i \text{ is hired} \ 0 & \text{otherwise} \end{cases} $$
The total number of hires is:
$$ X = \sum_{i=1}^{n} X_i $$
By the linearity of expectation:
$$ E[X] = E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i] $$
Now, candidate $i$ is hired exactly when they are the best among the first $i$ candidates. Since the order is random, candidate $i$ is equally likely to be the best, second-best, …, or worst among these $i$ candidates. So the probability that candidate $i$ is the best of the first $i$ is:
$$ P(X_i = 1) = \frac{1}{i} $$
Since $X_i$ is an indicator variable, $E[X_i] = P(X_i = 1) = \dfrac{1}{i}$. Putting this together:
$$ E[X] = \sum_{i=1}^{n} \frac{1}{i} = \ln n + O(1) $$
This is the harmonic number $H_n$, and it tells me that even though I might hire all $n$ candidates in the worst case, I expect to hire only about $\ln n$ candidates if the order is random. This is a dramatic improvement — logarithmic instead of linear.
If I compute the total expected cost, with $c_i$ as the interview cost per candidate and $c_h$ as the hiring cost:
$$ E[\text{total cost}] = n \cdot c_i + c_h \cdot \ln n $$
Diagrams
flowchart TD
A[Start: no current hire] --> B[Interview next candidate]
B --> C{Better than current hire?}
C -- Yes --> D[Hire candidate, pay hiring fee]
D --> E[Update current best hire]
E --> F{More candidates?}
C -- No --> F
F -- Yes --> B
F -- No --> G[Stop: final hire is current best]
Pseudocode
HIRE-ASSISTANT(candidates[1..n])
best = candidate with rank 0 // a placeholder worse than everyone
totalCost = 0
for i = 1 to n
totalCost = totalCost + interviewCost
if candidates[i] is better than best
best = candidates[i]
totalCost = totalCost + hiringCost
return best, totalCost
RANDOMIZE-HIRE-ASSISTANT(candidates[1..n])
RANDOMLY-PERMUTE(candidates)
return HIRE-ASSISTANT(candidates)
Step-by-Step Example
Suppose I have 5 candidates arriving in this order, ranked from 1 (worst) to 5 (best): [3, 1, 4, 2, 5].
- Candidate 3 arrives: no current hire, so I hire them. Hires = 1.
- Candidate 1 arrives: rank 1 is worse than rank 3, so I don’t hire them.
- Candidate 4 arrives: rank 4 is better than rank 3, so I hire them. Hires = 2.
- Candidate 2 arrives: rank 2 is worse than rank 4, so I don’t hire them.
- Candidate 5 arrives: rank 5 is better than rank 4, so I hire them. Hires = 3.
Final hire: candidate ranked 5 (the best). Total hires in this run: 3, out of a theoretical worst case of 5.
Time Complexity
- Best case: $O(n)$ — I still have to interview every candidate once, even if I only ever hire the first one (which happens when the first candidate is already the best).
- Average case (random order): $O(n)$ for interviewing, plus an expected $O(\log n)$ hiring operations, so the dominant cost of the loop itself is still $O(n)$, but the number of hires — often the more expensive operation — is $O(\ln n)$ in expectation.
- Worst case: $O(n)$ interviews and up to $n$ hires, so $O(n)$ hiring operations in the worst case.
Space Complexity
The algorithm only needs to remember the current best candidate and a running cost counter, so the space complexity is $O(1)$ auxiliary space, aside from the $O(n)$ space needed to store the input list of candidates itself.
Correctness Analysis
The algorithm is correct by a simple invariant: after processing the first $i$ candidates, “current best hire” always holds the best candidate seen among the first $i$. This is trivially true after processing candidate 1, and each subsequent step preserves it, because I only update the current best when a strictly better candidate appears. By induction, after all $n$ candidates are processed, the current best hire is the best candidate overall.
Advantages
- It’s a clean, minimal model for understanding probabilistic analysis and indicator random variables.
- It directly motivates the use of randomization — if I can’t guarantee random input, I can randomly permute it myself to guarantee good expected behavior.
- The math generalizes to many other “record-counting” problems in computer science and statistics, like analyzing the number of local maxima in random sequences.
Disadvantages
- It’s an idealized model — in reality, “better” isn’t always a strict, total order, and interview outcomes are noisy.
- Randomizing input order isn’t always possible or appropriate in real hiring, or in some real-world systems where sequence matters for other reasons.
- The model assumes each candidate can only be evaluated once and interviewed in a fixed sequence, which doesn’t capture batch decision-making.
Applications
- Analyzing algorithms like randomized quicksort, where a similar counting-of-records argument is used to bound expected running time.
- Online algorithms and the classic “secretary problem,” a close cousin of the hiring problem used in optimal stopping theory.
- Any streaming scenario where I must decide immediately, without going back, such as accepting or rejecting bids, offers, or requests as they arrive.
- Teaching foundational tools — linearity of expectation and indicator random variables — used throughout randomized algorithm design.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Simulates the hiring problem.
ranks[] holds the candidates in the order they are interviewed.
Higher rank means a better candidate. */
int hireAssistant(int ranks[], int n, int interviewCost, int hiringCost, int *totalCost) {
int bestRank = -1; /* no hire yet, so this is worse than any real rank */
int bestIndex = -1;
int hires = 0;
*totalCost = 0;
for (int i = 0; i < n; i++) {
*totalCost += interviewCost; /* every candidate is interviewed */
if (ranks[i] > bestRank) {
bestRank = ranks[i];
bestIndex = i;
*totalCost += hiringCost; /* pay the fee to hire this candidate */
hires++;
}
}
printf("Total hires made: %d\n", hires);
return bestIndex; /* index of the final, best hire */
}
/* Fisher-Yates shuffle to randomly permute the candidate order,
turning any input into a randomized algorithm. */
void randomPermute(int arr[], int n) {
for (int i = n - 1; i > 0; i--) {
int j = rand() % (i + 1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int main() {
int n = 10;
int ranks[10];
for (int i = 0; i < n; i++) ranks[i] = i + 1; /* ranks 1..10 */
srand((unsigned int)time(NULL));
randomPermute(ranks, n);
printf("Candidate order: ");
for (int i = 0; i < n; i++) printf("%d ", ranks[i]);
printf("\n");
int totalCost;
int bestIndex = hireAssistant(ranks, n, 10, 100, &totalCost);
printf("Best candidate hired has rank: %d\n", ranks[bestIndex]);
printf("Total cost: %d\n", totalCost);
return 0;
}
Sample Input and Output
Given 10 candidates with ranks 1 through 10, randomly shuffled by the program, a typical run might look like:
Candidate order: 4 7 1 9 3 10 2 6 8 5
Total hires made: 4
Best candidate hired has rank: 10
Total cost: 500
The exact numbers will vary each run since the order is randomized, but the number of hires should hover around $\ln(10) \approx 2.3$, consistent with the theoretical expectation.
Optimization Techniques
- Randomize the input: If I can’t control the arrival order of real data, applying a Fisher-Yates shuffle before running the algorithm guarantees the expected $O(\ln n)$ hiring behavior regardless of the original order.
- Early termination: If I know the maximum possible rank in advance (e.g., a known upper bound on quality), I can stop early the moment I hire that maximum-ranked candidate, since no one better can ever arrive.
- Batch interviewing: In systems where I can review a batch of candidates before, deciding could reduce total hiring fees at the cost of losing the “immediate decision” property, though this changes the problem into a different one entirely (offline selection).
Common Mistakes
- Assuming the worst-case cost ($O(n)$ hires) is also the typical cost — many learners forget that random-order analysis gives a much smaller expected number of hires.
- Forgetting to apply linearity of expectation correctly — indicator random variables only work cleanly because expectation is linear even when the $X_i$ are not independent.
- Confusing “hiring cost” with “interview cost” — the interview cost is paid for every candidate, but the hiring cost is only paid when a new best is found.
- Mixing up the direction of “better” — some implementations, especially in code, accidentally hire someone worse due to a flipped comparison operator.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd/4th Edition, Chapter 5: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- MIT OpenCourseWare, “Introduction to Algorithms” Lecture on Probabilistic Analysis: https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/
- Wikipedia, “Secretary problem”: https://en.wikipedia.org/wiki/Secretary_problem
- Motwani and Raghavan, Randomized Algorithms, Cambridge University Press: https://www.cambridge.org/core/books/randomized-algorithms/0E9F0C0A5B0C2C0A9F0A0E0A0E0A0E0A
