Hacker News Reader

Comment by 13of40 | Hacker News Reader

When I worked there in the early 2000's I had a friend of a friend whose fiancée graduated with a bachelor's degree in either CS or EE and applied for a developer position. Somehow, and I struggle to understand the mechanics of this because engineering was highly compartmentalized away from the "business" parts of the business, they managed to turn her down for an engineering role and got her a job in marketing.

Also, the manhole cover question was considered déclassé as early as 1999. One that was still making the rounds was...let's see if I can remember this... You have a soda machine that has three buttons, Coke, Pepsi, and Random (Coke or Pepsi). You know that your trickster coworker has swapped all of the button labels, so none of them are correct. What's the optimal strategy for getting a Coke out of the machine?

View on HN

That was actually fun to think through for a minute. Easy, but I can see how a young me nervous at an interview might have stumbled.

Its why I hate those things. They aren't testing analytical or creative ability, they are testing grace under pressure - a quality I have found is gained through experience.

It depends on your definition of optimal. If you optimize for time, then pressing each button one at a time until a Coke comes out. Plus it doesn't take any brain cells so I can get back to coding quicker. : )

You can also optimize for

- The highest likelihood of getting your choice with a single pick

- The least amount of money spent to guarantee getting your choice

If you take as given, "none of them are correct," I think both of those optimisations still start with pressing Pepsi. It is either Coke or random, so you have about a 75% chance of getting what you want on the first press.

If none of them are correct, then

- pepsi is coke or random

- coke is pepsi or random

- random is coke or pepsi

If you want Coke and you start with Pepsi, you'll get back Coke (1/2 + 1/2x1/2) or Pepsi (1/2x1/2). However, you could pick it and get back Pepsi 10 times in a row.

If you start by picking Random, you get back Coke (1/2) or Pepsi (1/2). If you get back Pepsi, you know

1. Random = Pepsi 2. Coke = Random (since it can no longer be Pepsi, since Random is) 3. Pepsi = Coke

So, you get back Coke on your first attempt (1/2), or you get back Coke on your second attempt (1/1).

So picking random first, then the correct one, optimizes for lowest upper bound on the number of choices to get what you want. Which is _actually_ what I meant by "The least amount of money spent to guarantee getting your choice", but didn't actually express correctly.

> If you want Coke and you start with Pepsi, you'll get back Coke (1/2 + 1/2x1/2) or Pepsi (1/2x1/2). However, you could pick it and get back Pepsi 10 times in a row.

Why would you push it ten times in a row? If you get a Pepsi from it on your first press, you now know:

- The button labeled Pepsi is actually Random (it can't be the actual Pepsi button, since none of the labels are correct, and it's also not the Coke button)

- Therefore, the button labeled Coke is actually Pepsi (it can't be Coke by rule, and it's also not Random since we know where Random is now)

- Therefore, the button labeled Pepsi is actually Coke (elimination)

So the max is still 2 steps, but you have 75% chance of getting a Coke on the first try instead of just 50% chance. Same lower bounds, but better expected value.

If you hit the Pepsi button and get Pepsi, you know it's random, so the random button has to be Coke (and Coke gives Pepsi). So picking the Pepsi button first still works in two tries - you either get a Coke all the time, get it randomly on the first try, or figure out which button gets you Coke.

Whoops, good point.

At a quick glance, everyone in this thread seems to be assuming 'random' gives you Coke or Pepsi with equal probability ….

Regardless of the probability distribution of the random button, it does not change the optimal strategy. By pressing the Pepsi button, you are either going to get Coke (you "win") or Pepsi (so you know the button is random and you "win" by pressing random on the next go which you now know is Coke).

> Regardless of the probability distribution of the random button, it does not change the optimal strategy.

I agree, and didn't mean to suggest otherwise. I was just referring to the specific probability computations being made.

>You have a soda machine that has three buttons, Coke, Pepsi, and Random (Coke or Pepsi). You know that your trickster coworker has swapped all of the button labels, so none of them are correct. What's the optimal strategy for getting a Coke out of the machine?

I prefer Pepsi to Coke, so I wouldn't attempt to get a Coke. The optimal strategy is, of course, to get a crowbar, pry the machine open and take what you want.

That's the optimal, least expensive strategy -- assuming you have access to a crowbar.

I really think the answer for all of those kinds of questions should be "I'd use Google to find the answer". I mean who would try and solve a problem like that without searching for a solution first?

Edit: http://mathpuzzlewiki.com/index.php/Soda_machine

If you're being interviewed for a job at Microsoft the answer should be "I'd use Bing to find the answer."

When I interviewed in Redmond in 2011, they actually told us this in the pre-interview orientation session!

Does anything beat just pressing the buttons in order?

This is essentially the Monty Hall problem. First choice is 1/3d to be correct, if this choice is wrong, then change, because you will now improve your odds to be 1/2

Maybe I am misunderstanding but the question says NONE of the labels are correct right? If so, I was thinking of it this way. If you press coke, it can only be random or Pepsi (.25?), if you press Pepsi, it can only be coke or random (.75?), if you press random it can only be coke or Pepsi (.5) (oddly this is still random 50/50 :) ). So the optimal on first try would be to press Pepsi?

This was actually my first-glance answer. Consider that the Pepsi label can't possibly be the Pepsi button, but the other two can.

And if that first press fails, the Pepsi label must be the Random button, so you should press the button with the Random label as it is guaranteed to be the Coke button.

You press random and taste, lets say it comes out pepsi. This means that this button has to be the pepsi button because if it was the random button then the label would be correct, like you mentioned. This settles the pepsi button.

Regarding the other two buttons, one is random and the other is coke but their labels are pepsi and coke, giving us only two possible (order-independent) states which I'll illustrate with the format drink(label)/drink(label):

Coke(Pepsi)/Random(coke)

Coke(Coke)/Random(Pepsi)

The second case is invalid because it would require for the coke label to be correct, leaving only one possible case: the button labeled pepsi would have to give out coke.

Both methods are fine.

Let's say you press the Random button first. If it is actually the Coke button, you get a Coke, and you can stop. Otherwise it's actually the Pepsi button, then you press the Pepsi button since that is actually the Coke button. So you get a Coke in one or two button presses.

Basically there are only two permutations of buttons possible, because all other permutations are disqualified by the "not the same as before" rule. Since the goal is specifically to get a Coke in the fewest button presses, you just have to not start with the Coke button since that is the least likely to produce a Coke.

No, you an apply more reasoning to it up front. If "none of them are correct" then you press 'surprise' first, and you either get the drink you wanted that time, or on your next guess.

I worked this out for the version of the problem on the linked pages but I must have misread the one posted here.

If the labels are all incorrect, you would want to start with the one labelled with the drink you don't want. This would give you an initial chance of 75% of getting the drink you do want (.5 + .25). If you don't get it on the first press, then you would press the one labelled "random", as this would 100% be the drink that you do want.

In Monty Hall Game you improve your odds to be 2/3, not 1/2. If you think the staying door wins 1/3 of the time and the switching door 2/3, where is the car located in the 1/6 missing?

IIRC, optimal was measured by how many quarters you put in the machine.

Smashing the machine?

Yes.

rot13:

Bcgvzny fgengrtl vf gb fryrpg "enaqbz", gura vs lbh trg n Crcfv, fryrpg "Crcfv". Gjb cerffrf znk

Nsgre fryrpgvat "Enaqbz":

* lbh trg n Pbxr (1 cerff)

* Lbh trg n Crcfv

Vs lbh trg n Crcfv, lbh xabj gung "enaqbz" vf gur ohggba juvpu nyjnlf cebqhprf n "Crcfv" (bayl "Crcfv" be "Enaqbz" pna cebqhpr n Crcfv, naq lbh xabj gur ynoryf ner jebat).

Sebz urer, lbh xabj gung gur ohggba ynoryyrq "Pbxr" pna'g cebqhpr n "Pbxr", nf gur ynoryf ner fjvgpurq. Vg pna'g cebqhpr n "Crcfv", nf jr'ir sbhaq gung ohggba, fb vg zhfg or "enaqbz".

Gurersber, cerffvat "Crcfv" ba gur frpbaq gel jvyy nyjnlf trg lbh n "Pbxr"

See https://news.ycombinator.com/item?id=27933080 for a better strategy.

Ask my coworker which one is coke

Reply on news.ycombinator.com