Problem Description:We dont want to interview all the candidates in order to get the best one also do not wish ti hire and fire as we find better applicants.Instead we are willing to settle for a candidate who is close to the best.In this problem we must obey one company requirement:after each interview we must either immediately offer the position to the applicant or must tell them they will not get the job.what is the trade-off between minimizing the amount of interviewing and maximizing the quality of the candidate hired?

On-Line-Hiring-Max(k,n)
bestscore <-- ---inf
for i <--1 to  k
      do if score(i)>bestscore
                       then bestscore <----score(i)
for i <--k+1 to n
      do if score(i)>bestscore 
                            then return i
return n

we wish to determine for each possible value of k, the probability that we hire the most qualified applicant.
Let Si be the event that we succeed in choosing the best-qualified applicant in the ith one interviewed.
Pr(s)=sigma(i=k+1,n){Si} PR(Si)=k/(n(i-1)) 
=k/n*sigma(i=k,n-1)1/i Pr(s)>=1/e           say lnk=lnn-1,Max.

This is a much easier way than Nju_Mcm_Training_Professor Yao's method.

appended question.  How we can get the best expect applicant? The average expect rank?