Given the numbers 1 to 1000, what is the minimum number [of] guesses needed to find a specific number if you are given the hint ‘higher’ or ‘lower’ for each guess you make?
This may be considered a trick question, since it’s deceptively easy. Read the question carefully and you’ll note that the question asks for the ‘minimum’ number of guesses. Think about it – someone can guess the right question on their first try right?
So, the answer here would be ‘1’, since it would take only one correct guess to find a specific number.
Finding the maximum number of guesses
But, what if we wanted to find the maximum number of guesses?
Well, think about this one. What if the number that you have to guess is ‘1’ and you start guessing from 1,000? Then, if the person who knows the number keeps saying lower, then you would guess 999,998,997…6,5,4,3,2, and finally until you get to 1.
Subscribe to our newsletter on the left to receive more free interview questions!
The maximum number of guesses
This means that the maximum number of guesses is 999.
But, you must be saying, that’s a stupid answer – because no one would take that approach to guessing unless they were really foolish.
Using Binary Search
The approach most programmers would take is dividing the set of numbers in half and then working accordingly – basically a binary search as it is known in computer science.
So, let’s say the number you were trying to guess is a ‘1’. Then, you would start from the middle of 1,000 – which is 500. The person giving you hints would keep saying lower – and you would end up with something like this sequence of numbers:
Counting the number of guesses above would give you 10. Another way of arriving at this estimate would be to take the log base 2 of 1,000 – which would also give you approximately 10. Since you can’t possibly have a fraction of a guess, the result of log base 2 of 1000 should be rounded up to a whole number. Log base 2 of 1000 actually gives 9.965, but we round that up to 10 to get an integer.
