https://blog.jgc.org/2024/09/steve-ballmers-binary-search-interview.html John Graham-Cumming's blog 2024-09-03 Steve Ballmer's incorrect binary search interview question In this short video Steve Ballmer talks about a puzzle question he would ask candidates interviewing at Microsoft. Solving it is based on binary search and the expected value. Here's what he says: "I'm thinking of a number between 1 and 100. You can guess, after each guess I'll tell you whether high or low. You get it the first guess I'll give you five bucks. Four bucks, three, two, one, zero, you pay me a buck, you pay me two, you pay me three ". The question is "Should you accept to play this game?". In the interview, Ballmer states that the answer is "No" for two reasons: firstly, because he can pick numbers that'll be the most difficult for you to determine, secondly because the expected value of the game (assuming Ballmer chooses randomly) is negative: you end up paying Ballmer. He's right on the first count. If you follow a binary search strategy (which will be optimal if he's choosing randomly) and he chooses one of 2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 85, 87, 90, 93, 96, 98 or 100 then you owe him $1. For all other numbers you get $0 (if he chose 1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 86, 89, 92, 95 or 99) or a positive outcome (some of his money!). In the video above Ballmer chooses 59 which a binary search strategy would have found in 5 steps resulting in the interviewer, Emily Chang, winning $1. She was actually pretty close to doing that. The binary search steps would be 50, 75, 62, 56, 59 and she guessed 50, 75, 60, 55, 57, 58, 59. On the second count (Baller implies the expected value is negative), if he's choosing randomly, then he's wrong. The expected value is $0.20 (calculated discretely using the code below). The code calculates the number of guesses for each value and an overall expected value assuming Ballmer chooses randomly. use strict; use warnings; my @v = (0, 5, 4, 3, 2, 1, 0, -1, -2); my $ev = 0; my $ec = 0; my @range = (1..100); foreach my $r (@range) { my $l = $range[0]; my $h = $range[$#range]; my $s = 0; while (1) { $s += 1; my $g = int(($l + $h)/2); if ($r == $g) { print "$r found in $s steps (" . dollar($v[$s]) . ")\n"; $ev += $v[$s]; $ec += 1; last; } if ($g < $r) { $l = $g + 1; next; } if ($g > $r) { $h = $g - 1; next; } } } $ev /= $ec; print "Game expected value is " . dollar($ev) . "\n"; sub dollar { my ($d) = @_; my $f = (int($d) == $d)?'%d':'%.2f'; return sprintf("%s\$$f", ($d<0)?'-':'', abs($d)); } This chart shows the expected winnings (or loss) depending on the number Ballmer chooses. The shape of the binary search can be seen in the chart itself. [bs-1] A different way to think about the expected value and binary search is as follows: 1. On the first guess you choose 50 and win $5 with a probability of 1/100 2. On the second guess you choose 25 or 75 and win $4 with a probability of 2/100 3. On the third guess you choose 12, 37, 62 or 88 and win $3 with a probability of 4/100 4. On the fourth guess you choose 6, 18, 31, 43, 56, 68, 81 or 94 and win $2 with a probability of 8/100 5. And so on. The gives the expected value as 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100 (note the last term is the remaining possible numbers having reached the end of the binary search). That's 0.2. Why was Ballmer wrong? One possibility is that he didn't mean to have the $0 for 6 guesses. If he'd said "I'm thinking of a number between 1 and 100. You can guess, after each guess I'll tell you whether high or low. You get it the first guess I'll give you five bucks. Four bucks, three, two, one, you pay me a buck, you pay me two, you pay me three" then the expected value is -$0.49. at September 03, 2024 Email ThisBlogThis!Share to TwitterShare to FacebookShare to Pinterest Labels: mathematics, pseudo-randomness 5 comments: [blo] Damian Cugley said... Without bothering to think about it proper ,I wonder whether a different guessing algorithm do better, knowing which numbers he is likely to guess based on trying to get the highest payout? Like would an asymmetric binary chop? 1:14 PM [icon_delet] [bla] [IMG] Paul Hankin said... This comment has been removed by the author. 2:16 PM [icon_delet] [blo] royalroad said... Your answer to the interview question is also wrong. What ballmer is describing is an incomplete information game of two players. The correct way to calculate the optimal expected value is by finding a nash equilibrium. 2:19 PM [icon_delet] [bla] [IMG] Paul Hankin said... This comment has been removed by the author. 2:23 PM [icon_delet] [blo] espadrine said... Another (hopefully wrong) interpretation is that Ballmer implied he would change his secret number on the way, such that if using proper binary search, the Emily Chang attempt would have become: 50, 75, 62, 56, 59, 60, 61. If this is an adversarial game, this would be optimal play for him. I am not sure what else his remark that he can pick numbers that are hard to guess, means otherwise, in a Nashway equilibrium view. 4:38 PM [icon_delet] Post a Comment Older Post Home Subscribe to: Post Comments (Atom) Labels * pseudo-randomness * hardware * babbage * anti-spam * gnu make * retro * security * codes and ciphers * the geek atlas * mathematics * minitel * behind the screens * popfile * privacy * radio Popular Posts * [AEn0k_vWWj] Steve Ballmer's incorrect binary search interview question In this short video Steve Ballmer talks about a puzzle question he would ask candidates interviewing at Microsoft. Solving it is based on b... * [AEn0k_uoDF] Controlling the Taylor Swift Eras Tour wristbands with Flipper Zero Many large concerts feature wristbands that light up on command. They are used to produce varied visual effects across a stadium. One compan... * [casio1] Pimping my Casio with Oddly Specific Objects' alternate motherboard and firmware Some time ago I bought a replacement motherboard for my classic Casio F-91W from Crowd Supply. The project keeps the original Casio LCD but... * [proposal-1] The original WWW proposal is a Word for Macintosh 4.0 file from 1990, can we open it? The W3C has a page with the original WWW proposal from Tim Berners-Lee. One of the downloads says The original document file (I think - I ... * [mac-1] My daily driver is older than I thought; it's positively vintage! I was doing some clean up on my main laptop and realized it had been a while since bought a new computer. Turns out it was a lot older than ... * [Picture] Your last name contains invalid characters My last name is "Graham-Cumming". But here's a typical form response when I enter it: Does the web site have any idea how rud... * [light-sens] Two ways to use an LED as a light sensor with Arduino I needed to log when a light switched on and off during the night as part of debugging an oddly behaving movement sensor. To do that I built... * [tsb-1] "Hacker News" for retro computing and gaming I noticed over time that I was drawn to the retro computing or gaming posts on Hacker News . So, I've set up a dedicated web site in the... * [acs-1] Acorn Computer Systems catalogue circa 1983 I unearthed a catalogue that I'd picked up in around 1983 of Acorn Computer Systems . This catalogue overlaps the BBC Micro era (which w... * [701c-39] Complete restoration of an IBM "Butterfly" ThinkPad 701c Just over a year ago there was a discussion on Hacker News about the IBM ThinkPad 701c (the one with the lovely folding "butterfly &quo... Blog Archive * V 2024 (12) + V September (1) o Steve Ballmer's incorrect binary search interview ... + > June (3) + > May (1) + > April (1) + > March (3) + > February (2) + > January (1) * > 2023 (30) + > December (2) + > November (5) + > October (3) + > September (4) + > August (1) + > July (5) + > June (1) + > May (3) + > April (3) + > March (3) * > 2022 (24) + > December (2) + > November (3) + > October (8) + > September (1) + > July (2) + > June (2) + > April (2) + > March (4) * > 2021 (6) + > November (1) + > July (1) + > May (2) + > April (1) + > January (1) * > 2020 (2) + > June (2) * > 2018 (2) + > December (2) * > 2017 (4) + > May (1) + > April (3) * > 2016 (11) + > November (1) + > September (1) + > July (2) + > June (1) + > May (3) + > April (1) + > March (2) * > 2015 (11) + > November (1) + > July (2) + > May (1) + > April (5) + > March (1) + > January (1) * > 2014 (4) + > November (2) + > July (1) + > June (1) * > 2013 (39) + > September (4) + > August (1) + > July (4) + > June (2) + > May (5) + > April (12) + > March (3) + > February (2) + > January (6) * > 2012 (77) + > December (3) + > November (6) + > October (6) + > September (7) + > August (6) + > July (6) + > June (8) + > May (4) + > April (9) + > March (7) + > February (9) + > January (6) * > 2011 (79) + > December (5) + > November (7) + > October (2) + > September (5) + > August (2) + > July (8) + > June (10) + > May (6) + > April (9) + > March (6) + > February (12) + > January (7) * > 2010 (95) + > December (13) + > November (9) + > October (16) + > September (19) + > August (2) + > July (9) + > June (12) + > May (1) + > April (1) + > March (4) + > February (2) + > January (7) * > 2009 (31) + > December (1) + > November (8) + > October (3) + > September (6) + > August (9) + > June (1) + > May (1) + > January (2) * > 2008 (19) + > December (2) + > September (1) + > June (3) + > May (3) + > March (2) + > February (6) + > January (2) * > 2007 (34) + > December (2) + > November (3) + > October (5) + > August (2) + > July (2) + > June (4) + > May (3) + > April (1) + > March (6) + > February (4) + > January (2) * > 2006 (25) + > December (2) + > November (2) + > October (3) + > September (5) + > July (1) + > June (1) + > April (6) + > February (1) + > January (4) * > 2005 (3) + > December (1) + > November (2) Copyright (c) 1999-2024 John Graham-Cumming. Awesome Inc. theme. Powered by Blogger.