Hire Assistant
Suppose that you need to hire a new office assistant. Your previous attempts at
hiring have been unsuccessful, and you decide to use an employment agency. The
employment agency sends you one candidate each day. You interview that person
and then decide either to hire that person or not. You must pay the employment
agency a small fee to interview an applicant. To actually hire an applicant is more
costly, however, since you must fire your current office assistant and pay a substan-
tial hiring fee to the employment agency. You are committed to having, at all times,
the best possible person for the job. Therefore, you decide that, after interviewing
each applicant, if that applicant is better qualified than the current office assistant,
you will fire the current office assistant and hire the new applicant. You are willing
to pay the resulting price of this strategy, but you wish to estimate what that price
will be.
HIRE-ASSISTANT(n) 1 best = 0 //candidate 0 is a least-qualified dummy candidate 2 for i = 0 to n 3 do interview candidate i 4 if candidate i is better than candidate best 5 then best = i 6 hire candidate i For us hiring is much more costly than interview. So we interview everybody. Candidate i has probability of 1/i being the better than the previous 1..i-1 employees we have interviewed.
1 n = A.length 2 let P[1..n] be a new array 3 for i=1 to n 4 P[i] = RANDOM(1,n^3) 5 sort A, using P as sort keys O(n lg n)
RANDOMIZE-IN-PLACE(A) 1 n = A:length 2 for i=1to n 3 swap A[i] with A[RANDOM(i, n)] |
|