Re:Steve Ballmer's incorrect binary search interview question
by corecirculator on Tuesday September 03, 2024 @10:26AM
(#41435303)
Other commenters are wrong in saying that the payout is different for an adversarial choice.
The crux of the payout derivation is: we can only cover 1 number in step 1, 2 in step 2, 4 in step 3, 8 in step 4, and so on. You can choose your initial number in binary search randomly, and as long as you meet the above condition is met (# of possible numbers covered in each step), payout should be same as 0.2
[ Parent
| on HN ]
Re:Steve Ballmer's incorrect binary search interview question
by dagw on Tuesday September 03, 2024 @11:13AM
(#41435736)
If I 'know' that my opponent is adversarial, then I might assume that he's not picking from the set of 100 possible numbers, but actually from a smaller set of 'adversarial' numbers, like the set that will always take 6 or 7 guesses using the naive binary search approach, and I can adjust my strategy accordingly.
Re:Steve Ballmer's incorrect binary search interview question
by LudwigNagasena on Tuesday September 03, 2024 @05:54PM
(#41439685)
You should assume that your opponent is adversarial to your specific strategy.
Re:Steve Ballmer's incorrect binary search interview question
by alexey-salmin on Tuesday September 03, 2024 @10:52AM
(#41435535)
Your calculation assumes that probability of each number is the same which is not true for adversarial choice.