The hiring problem
Candidates arrive one by one and anyone better than everyone before is hired; how many hires do we make?
We want to hire an assistant. Candidates arrive one at a time, and after each interview we must decide on the spot. Our policy: if the candidate is better than everyone before, hire them (and let the previous one go). Hiring is expensive; how many times do we hire?
Read the full explanation ↓- Time:
n interviews; about ln n hires on average for a random order - Space:
O(1) - CLRS, section 5.1
Ten candidates in a mixed order; only four are hired.
def hire_assistant(ranks):best = -1hired = []for i in range(len(ranks)):if ranks[i] > best:best = ranks[i]hired.append(i)return hired
Start
Local variables
Orange = changed in this step
ranks list
Call stack
- hire_assistant()line 1
How the work grows with input size
Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.
- hire
- current input (n=10)
Show as a table
| n | hire |
|---|---|
| 4 | 1.7 |
| 6 | 2.3 |
| 8 | 3.1 |
| 10 | 2.9 |
| 12 | 3.5 |
| 14 | 3.2 |
| 16 | 3.4 |
Explanation
The problem
We want to hire an assistant. Candidates arrive one at a time, and after each interview we must decide on the spot. Our policy: if the candidate is better than everyone before, hire them (and let the previous one go). Hiring is expensive; how many times do we hire?
Analysis
- Worst case: the candidates arrive in increasing order, and every one is hired:
nhires. - If the order is random, candidate
ibeats all before with probability1/i. So the expected number of hires is1 + 1/2 + … + 1/n ≈ ln n: about 5 hires for 100 candidates.
This is CLRS's classic example of probabilistic analysis, and it shows why we sometimes shuffle the input ourselves (a randomized algorithm).
What to watch in the trace
- The
iarrow is the current candidate, and thehiredlist is in the memory panel. - Compare the number of
hiresteps on "increasing" and on the "textbook-style example".