Secretary Problem(en.wikipedia.org)
en.wikipedia.org
Secretary Problem
https://en.wikipedia.org/wiki/Secretary_problem
65 comments
I was asked a version of this as an interview question a few months ago. Despite recognizing the form of it immediately and giving some intuition for why it converges to 1/e, the interviewer had nothing else prepared and had expected it to be new to me, so he took me through a brutal one hour of his personal "guided proof" of the answer, including drawing a massive grid on a whiteboard and stepping through iterations. At one point I may have hinted that his method was overcomplicating things and tried to steer the conversation towards other aspects of the problem (ex: the time based formulation), no, let's get back on track with this grid. I didn't get the job, and I was specifically called out for doing poorly on that portion of the interview. I used to think this problem was really cool, now it just pisses me off remembering that situation.
On the positive side you dodged a bullet and wasted just a day. Imagine working for someone like that. Time you'll never get back.
Oh come on. Seems _highly_ probable he was stuck in an interview with a junior dev that only understood enough to follow the documented answer.
If a junior dev is interviewing candidates unsupervised in this organization, he still dodged a bullet.
It was a junior dev and this was the worst of it, but as I said elsewhere, looking back the whole thing was shitty. Whiteboard coding questions of the worst type from all levels, zero interest in my previous experience in a related area, and no respect for my time. It was an 8+ hour day and then they had the nerve to ask me to turn my car around and come back because they "forgot" to schedule me with someone senior. When I didn't get the position, they were borderline rude to my recruiter when he asked to get info on the decision ("He performed poorly in our case interviews, particularly [the one I posted about]"). And I had honestly thought I did pretty well considering what was being asked.
Huge company in my town and they do fairly well, so the whole thing left me feeling awful for about a month afterward, particularly the jab at my technical skills. Didn't mean to vent like this but I figure if anyone would understand it's people on HN. There is a happy ending: I got a new role a little while later and found multiple coworkers who also interviewed there with similar stories. So it wasn't just me.
Huge company in my town and they do fairly well, so the whole thing left me feeling awful for about a month afterward, particularly the jab at my technical skills. Didn't mean to vent like this but I figure if anyone would understand it's people on HN. There is a happy ending: I got a new role a little while later and found multiple coworkers who also interviewed there with similar stories. So it wasn't just me.
Eight hours, junior devs interviewing, pointless questions...
You can leave an interview at any time if you're not feeling it. You're not obligated to stick it out. I've bailed on interviews before. It sounds like you really wanted this job, though, so I understand wanting to see it through.
That's why I always ask candidates how they feel it's going so far when I begin an interview. Any issues on our end? You should be checking in with yourself at least between every interview to gauge how you feel. The vast majority of interviewers are shitty, so if you're not feeling great it's probably more on them than you.
You can leave an interview at any time if you're not feeling it. You're not obligated to stick it out. I've bailed on interviews before. It sounds like you really wanted this job, though, so I understand wanting to see it through.
That's why I always ask candidates how they feel it's going so far when I begin an interview. Any issues on our end? You should be checking in with yourself at least between every interview to gauge how you feel. The vast majority of interviewers are shitty, so if you're not feeling great it's probably more on them than you.
AN 8 HOUR INTERVIEW???!!! Holy fork!
I agree with the other folks that indicated you dodged a bullet.
Also: I'm sorry that there are folks in our industry that would submit you to such inhumane conditions. I'm also glad you stuck around in spite of this shiz.
I agree with the other folks that indicated you dodged a bullet.
Also: I'm sorry that there are folks in our industry that would submit you to such inhumane conditions. I'm also glad you stuck around in spite of this shiz.
well you could argue that's £400/500 - (say $600) down the drain as that's an average day rate for a contractor in the UK
Cost of doing business
so one that can be avoided by not interviewing for companies know to have broken recruitment processes
How do you know though? That's ok if you interview only for big companies where there is a lot of open dialogue about their recruitment.
Maybe you were the first person he interviewed.
It was one of the team members, not a manager or lead, so I would have been inclined to overlook it had it not been alongside 3 other "case interviews" that were tricky whiteboard coding/math problems in disguise. I think I spent a grand total of 20 minutes of my 8 hour day discussing my history and relevant experience.
the first n/e
Companies should really adopt shadow interviewing more. Go into an interview and watch someone experienced do it, so you can learn more about how to make interviews pleasant (even for a candidate that doesn't know what they're doing).
I’ve concluded 1:1 in person interviews are insta-fails. With out any witnesses, the bozo interviewing you will just do, say whatever. I’ve had a handful of experiences like the GP and there’s no recourse.
I've always liked this problem mathematically but I'd never used it for actual hiring (though I have happily used it for certain statistical sampling).
When actually hiring, I care about the time value of opportunity cost. That is, we interview and get hire the first candidate that we feel can do the job well and we all otherwise like, then the benefit of having her on the job ASAP exceeds any possibly value from another candidate that might show up some uncertain time later.
When actually hiring, I care about the time value of opportunity cost. That is, we interview and get hire the first candidate that we feel can do the job well and we all otherwise like, then the benefit of having her on the job ASAP exceeds any possibly value from another candidate that might show up some uncertain time later.
In addition to having more information -- you can measure (very approximately!) how good candidates are, rather than merely being able to rank them against each other (as in the Secretary Problem) -- the payoffs are different. For actual hiring, having the second-best out of 100 secretaries is still pretty good; while for the purposes of the Secretary Problem having the second-best out of 100 secretaries is just as bad as having the worst secretary.
There is some connection to real world hiring practices, but only if you abstract away enough: The solution to the Secretary Problem basically comes down to
1. Spend some time gathering information which will let you assess how strong future candidates are.
2. Use that information to help you decide whom to hire.
In some cases step 1 is solved by interviewing many candidates in parallel; but in most cases companies adjust their thresholds for what "good enough" is over time based on their observations of incoming candidates. They might very well reject a candidate early on and then regret that decision later once they realize that she was exceptional compared to a disappointingly weak candidate pool.
There is some connection to real world hiring practices, but only if you abstract away enough: The solution to the Secretary Problem basically comes down to
1. Spend some time gathering information which will let you assess how strong future candidates are.
2. Use that information to help you decide whom to hire.
In some cases step 1 is solved by interviewing many candidates in parallel; but in most cases companies adjust their thresholds for what "good enough" is over time based on their observations of incoming candidates. They might very well reject a candidate early on and then regret that decision later once they realize that she was exceptional compared to a disappointingly weak candidate pool.
To be fair, that is a restatement of the problem into a much more difficult one. Instead of looking for the best candidate among N, you are looking to maximize net-present-value of the work product produced by a candidate selected from a pool of N presented over time.
So you need not just a discrete better/worse comparison of candidates, but some linear measure of each candidate's productivity, some value for the work product, and an interest rate.
So you need not just a discrete better/worse comparison of candidates, but some linear measure of each candidate's productivity, some value for the work product, and an interest rate.
Several mobile strategy games like Clash of Clans present this problem when raiding. You can skip to the next base or raid the current base.
Numberphile did a nice presentation of this problem and a solution here: https://www.youtube.com/watch?v=ZWib5olGbQ0
Numberphile did a nice presentation of this problem and a solution here: https://www.youtube.com/watch?v=ZWib5olGbQ0
When actually hiring, you also have benchmarks that aren't purely relative, and past experience to fall back on.
> When actually hiring, you also have benchmarks that aren't purely relative, and past experience to fall back on.
(This problem is framed as hiring the best which I assume means closest to optimal weights on those non-relative benchmarks -- whatever "optimal" means.)
But your comment is interesting, as this problem was originally as "the wife problem": how do "you" -- presuming incorrectly even at the time all mathematicians to be male -- find the optimal wife.
The thing that made your comment funny to me is that in majority of marriage cases (by anyone to anyone) neither party has much, or any past experience to fall back on!
(This problem is framed as hiring the best which I assume means closest to optimal weights on those non-relative benchmarks -- whatever "optimal" means.)
But your comment is interesting, as this problem was originally as "the wife problem": how do "you" -- presuming incorrectly even at the time all mathematicians to be male -- find the optimal wife.
The thing that made your comment funny to me is that in majority of marriage cases (by anyone to anyone) neither party has much, or any past experience to fall back on!
In those cases, even if you select poorly, you can change your weight and preferences afterward.
I ran into this problem many years ago when writing a memory allocator. Say you keep a list of free blocks. You don't keep them sorted, but you do keep track of how long the list is. You now need to find a block of at least size n but not much larger, and the free list is so long you'd rather not look through the whole thing for each allocation.
There are a bunch of ways to write memory allocators, but with the above constraints, it's the same problem.
There are a bunch of ways to write memory allocators, but with the above constraints, it's the same problem.
You can use this idea in the clock algorithm to approximate LRU.
I dated a guy once who, after a couple of weeks, asked me to marry him--citing this problem as his reasoning.
I said no.
Butt he's all I ever think about whenever I hear it mentioned, so.
I said no.
Butt he's all I ever think about whenever I hear it mentioned, so.
Was his name Michael? http://mat.tepper.cmu.edu/blog/?p=1392
Definitely a good call; I don't think I'd want to marry someone who thought they could evaluate my value as a future partner in a couple of weeks.
Did you ask his value for "n", and how he chose that value?
It was 2, and I honestly have no idea why
What? That makes it even weirder. That means you weren't even being chosen because you were considered to outperform anyone else. Either you were the first candidate, and no comparison could be made, or your were the last candidate, and had to be chosen anyway!
I was his second girlfriend, and he'd just gotten out of a multi-year relationship. We met while interning in SV. We broke up soon after I went back to school, and I think he just ended up getting back with his ex, so...
Ah, so once again, we have a situation where the documentation describes the use of an elegant algorithm, but the actual implementation is a random pile of hacks and heuristics slapped together by someone who seems not to have really understood what they were doing.
[deleted]
The questionable self help book 'Algorithms to Live By' could have prompted this. It's recommend in the first chapter
I like this explanation of the Secretary problem (aka optimal stopping problem) by @lpolovets [1]
> The basic problem is this: there are N applicants for a secretarial position. The applicants are interviewed in random order, and you must accept or reject a candidate immediately after interviewing them. After you reject someone, there's no way to bring them back. There is only one position available, so as soon as you accept a candidate you are done. What strategy should you pursue in order to maximize the likelihood of hiring the best candidate out of the N applicants?
> It turns out that the best strategy is to look at the first N/e applicants (i.e. the first ~37%), reject all of them, then accept the first applicant that is better than all of the initial rejects. It turns out this strategy has a ~37% (1/e) chance of picking the best candidate, regardless of how large N is. This is counterintuitive. It means that even if you have one billion applicants in some random order, you will find the very best one ~37% of the time with this strategy, even though you will (on average) make your choice without meeting the last few hundred million candidates.
> I think this has some interesting practical implications. For example, as a VC, one possible strategy that I can pursue is to look for interesting sectors (3D printing, drones, bitcoin, etc.) and try to invest in the very best startup in each of those sectors. The Secretary Problem is a decent approximation of this. I can go on AngelList and see that there are thirty 3D printing startups in LA/NYC/SF, which are the markets I'm interested in. One way to pick the best one of these 30 would be to meet 11 of these startups, pass on all of them, then invest in the next 3D printing startup I meet that's better than all of those. Of course, this would be a jerk move. I'd be wasting the time of a lot of founders if I knew I was planning to pass on their startups no matter what. However, if I happened to pass on a dozen 3D printing startups by chance, and I knew that there were ~30 in total, then if the 14th one was better than the first dozen, I would know there was a pretty good chance it was the best one out of all 30 even though I had yet to see the last 16.
[1] https://www.quora.com/Mathematics/What-are-the-most-interest...
> The basic problem is this: there are N applicants for a secretarial position. The applicants are interviewed in random order, and you must accept or reject a candidate immediately after interviewing them. After you reject someone, there's no way to bring them back. There is only one position available, so as soon as you accept a candidate you are done. What strategy should you pursue in order to maximize the likelihood of hiring the best candidate out of the N applicants?
> It turns out that the best strategy is to look at the first N/e applicants (i.e. the first ~37%), reject all of them, then accept the first applicant that is better than all of the initial rejects. It turns out this strategy has a ~37% (1/e) chance of picking the best candidate, regardless of how large N is. This is counterintuitive. It means that even if you have one billion applicants in some random order, you will find the very best one ~37% of the time with this strategy, even though you will (on average) make your choice without meeting the last few hundred million candidates.
> I think this has some interesting practical implications. For example, as a VC, one possible strategy that I can pursue is to look for interesting sectors (3D printing, drones, bitcoin, etc.) and try to invest in the very best startup in each of those sectors. The Secretary Problem is a decent approximation of this. I can go on AngelList and see that there are thirty 3D printing startups in LA/NYC/SF, which are the markets I'm interested in. One way to pick the best one of these 30 would be to meet 11 of these startups, pass on all of them, then invest in the next 3D printing startup I meet that's better than all of those. Of course, this would be a jerk move. I'd be wasting the time of a lot of founders if I knew I was planning to pass on their startups no matter what. However, if I happened to pass on a dozen 3D printing startups by chance, and I knew that there were ~30 in total, then if the 14th one was better than the first dozen, I would know there was a pretty good chance it was the best one out of all 30 even though I had yet to see the last 16.
[1] https://www.quora.com/Mathematics/What-are-the-most-interest...
The secretary problem and investing have one important difference that throws this all out the window - you can meet with multiple startups without rejecting them, and make a decision when you've met them all (or all the ones you want to meet). There's no requirement in the real world to accept/reject immediately post-interview without any possibility of recall.
> Of course, this would be a jerk move. I'd be wasting the time of a lot of founders if I knew I was planning to pass on their startups no matter what.
On a macro-level, this isn't a jerk move at all - the other way would have you 'waste' the time of 29 founders instead of 11.
> Of course, this would be a jerk move. I'd be wasting the time of a lot of founders if I knew I was planning to pass on their startups no matter what.
On a macro-level, this isn't a jerk move at all - the other way would have you 'waste' the time of 29 founders instead of 11.
No, the biggest problem is that nobody is perfect at ranking startups, period. And as proven by that "antiportfolio" page of a day or two ago, even generally successful VCs can't do that reliably.
Incredibly interesting, but I can't resist nitpicking!
The with extrapolating this to real life would be that it's making assumptions that are not realistic. For instance it assumes infinite granularity in candidates. In other words the rating of a candidate can be from 0 to infinity instead of the granularity we really see things in which is going to be closer to 0-4 or very bad/bad/neutral/good/very good.
It also assumes a normal distribution. Something that's perfectly reasonable for an unknown distribution, but in my experience the number of 'very good' candidates tends to be much larger than its equal but opposite 'very bad' end perhaps due to some sort of survivorship bias.
The with extrapolating this to real life would be that it's making assumptions that are not realistic. For instance it assumes infinite granularity in candidates. In other words the rating of a candidate can be from 0 to infinity instead of the granularity we really see things in which is going to be closer to 0-4 or very bad/bad/neutral/good/very good.
It also assumes a normal distribution. Something that's perfectly reasonable for an unknown distribution, but in my experience the number of 'very good' candidates tends to be much larger than its equal but opposite 'very bad' end perhaps due to some sort of survivorship bias.
I started listening to the audio book version of "Algorithms to Live By: The Computer Science of Human Decisions"[1] by Brian Christian and Tom Griffiths. It starts by talking about the Secretary Problem and the 37% rule and it is very entertaining how much of our daily problems are some variation of a small set of well known problems that have interesting (and often counter-intuitive) mathematically proofed solutions.
Before I get downvoted to hell, let me say THIS IS NOT AN AFFILIATE LINK, I will earn nothing if you click it (I hate spam as much as the next guy but people here tend to be a little trigger happy).
[1] https://www.audible.com/pd/Business/Algorithms-to-Live-By-Au...
Before I get downvoted to hell, let me say THIS IS NOT AN AFFILIATE LINK, I will earn nothing if you click it (I hate spam as much as the next guy but people here tend to be a little trigger happy).
[1] https://www.audible.com/pd/Business/Algorithms-to-Live-By-Au...
A previous thread: https://news.ycombinator.com/item?id=7337759.
If the chance you'll pick the best option is 37%, what is the chance you'll pick someone in the top 2, or the top 5?
Another way of asking is, does it raise the odds you'll get someone really good, even if they aren't the best?
Another way of asking is, does it raise the odds you'll get someone really good, even if they aren't the best?
I haven't calculated it exactly, but we were playing around with simulation code elsewhere among the comments, and my version [0] calculates the hiring frequency for each candidate, not just the best one, so you could look at the tail of the list called "hires".
[0] https://news.ycombinator.com/item?id=15573921
[0] https://news.ycombinator.com/item?id=15573921
Did not know about this, but I read a simplified version of it a long time ago, which said "carefully examine the first choice, reject it, then go for the first choice that is better." Apparently, this would give me an above average option in most cases (did not do the math).
I quite like that and sometimes use it, e.g. to decide which restaurant to have a meal in.
I quite like that and sometimes use it, e.g. to decide which restaurant to have a meal in.
The Power of Two Random Choices: it's a surprisingly decent heuristic
https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2...
https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2...
Oh interesting, thanks for sharing!
I did some analysis of this problem in Python here: https://imrankhan17.github.io/pages/Solving%20the%20secretar...
I'd really like a real-life example of this.
I can't help but think this is a solution in search of a problem.
I can't help but think this is a solution in search of a problem.
Case: You are wondering around a new city with few friends. Everybody is hungry and getting annoyed. No mobile devices are available or you do not trust the online recommendations. How do you find a good place to eat?
First you estimate based on the level of hunger, quality of shoes and the restaurant density of the area how many places you can check before you starve to death. This rule tells that you should first walk pass n/2.718 restaurants and then pick the best one you have seen so far.
First you estimate based on the level of hunger, quality of shoes and the restaurant density of the area how many places you can check before you starve to death. This rule tells that you should first walk pass n/2.718 restaurants and then pick the best one you have seen so far.
Almost correct but the secretary problem only allows you to accept or permanently reject an option. What you describe allows going back to previously rejected options.
That's a terrible contrivance. The real solution is to walk into the first place you can afford and enjoy the time with your friends. You don't need the best place to eat, you just need a good enough place to eat and a sense of humor or humility.
[deleted]
This is the awe inspiring bit:
> One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants.
Another example of how our intuitions are poor at probabilities.
100M! Might give that a Monty Carlo sim. Or even try it on a big DB table at work.
> One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants.
Another example of how our intuitions are poor at probabilities.
100M! Might give that a Monty Carlo sim. Or even try it on a big DB table at work.
There's probably no lack of toy code, but since I am a skeptic / sceptic, quick nonsense code for pythonistas : https://gist.github.com/anonymous/ef975cdcb26044de9ba93e4e74...
Guess what? Skepticism allayed!
Guess what? Skepticism allayed!
Nerd sniped. I couldn't help it. What do you think> :-)
from math import e, floor
from random import randint
def secretary_search(candidates):
"""Rejects first n / e candidates and then selects the first better."""
n_reject = int(floor(len(candidates) / e))
best = max(candidates[:n_reject])
for candidate in candidates[n_reject:]:
if candidate > best:
return candidate
return candidates[-1]
success = 0.0
size = 100
trials = 10000
for _ in range(trials):
candidates = [randint(1, 1000) for _ in range(size)]
success += max(candidates) == secretary_search(candidates)
print success / trialsMy version! [0]
- More functional, with iterators and stuff. (It's half-baked, though, so please take it further!)
- Handles small numbers of candidates correctly.
- Agrees with the table on Wikipedia [1], and with the 1/e limit.
- Calculates hiring frequency for all candidates, not just the best one.
- Faster!
[0] https://gist.github.com/anonymous/9d735c5c77bd2e0939c69f5dd4...
[1] https://en.wikipedia.org/wiki/Secretary_problem#Deriving_the...
- More functional, with iterators and stuff. (It's half-baked, though, so please take it further!)
- Handles small numbers of candidates correctly.
- Agrees with the table on Wikipedia [1], and with the 1/e limit.
- Calculates hiring frequency for all candidates, not just the best one.
- Faster!
[0] https://gist.github.com/anonymous/9d735c5c77bd2e0939c69f5dd4...
[1] https://en.wikipedia.org/wiki/Secretary_problem#Deriving_the...
This would feel much more interesting if there was a cost attached to being forced to hire a terrible candidate.
Isn't the cost that you get a terrible candidate?
Yes. That isn’t factored into the algorithms though.
Interestingly, it seems this has been discussed here before: http://www.thelowlyprogrammer.com/2010/04/introducing-marria...