News for hackers. Stuff that matters.
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
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.