Offensive Security Researcher & Quantum Cryptography Analyst

Probabilistic Analysis and Randomized Algorithms: The Hiring Problem Explained

Abdul Wahab Junaid
Probabilistic Analysis and Randomized Algorithms: The Hiring Problem

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:

How It Works

Here’s the procedure I use, step by step:

  1. I set my current best hire to “none” and my total hiring cost to zero.
  2. 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$.
  3. 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].

Final hire: candidate ranked 5 (the best). Total hires in this run: 3, out of a theoretical worst case of 5.

Time Complexity

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version