Re:Steve Ballmer's incorrect binary search interview question
by Someone on Tuesday September 03, 2024 @01:49PM
(#41437296)
> I'd be interested to see someone do the analysis of what the optimal random-offset-selection algorithm would be to counter trivial adversarial choice
If you know your opponent picks a number uniformly from all numbers that lead to a maximum of guesses, the optimum strategy is a binary search between those numbers, making sure to pick one of those numbers at each turn.
The problem stays completely symmetric under this condition, so there would be two (maybe four due to edge conditions) optimal first guesses summing to 101.
In general, I think the trick still is a binary search where each guess splits the range of options in halves of equal expected/min/max cost (depending on whether you want to optimize for expected/min/max cost).
If you know your opponent picks a number uniformly from all numbers that lead to a maximum of guesses, the optimum strategy is a binary search between those numbers, making sure to pick one of those numbers at each turn.
The problem stays completely symmetric under this condition, so there would be two (maybe four due to edge conditions) optimal first guesses summing to 101.
In general, I think the trick still is a binary search where each guess splits the range of options in halves of equal expected/min/max cost (depending on whether you want to optimize for expected/min/max cost).