Questions d'entretien
Entretien pour Software Engineer

MetaGiven the numbers 1 to 1000, what is the minimum numbers guesses needed to find a specific number if you are given the hint "higher" or "lower" for each guess you make.
Réponses aux questions d'entretien
32 réponse(s)
Nope, I don't think it's 63. It's a binary search as mentioned above. It should be about 10: Arbitrarily let's say the answer is 1000, so every time you guess, the response will be "no, it's higher". 1) 1  1000, guess 500. 2) 501  1000, guess 750. 3) 751  1000, guess 875. 4) 876  1000, guess 938. 5) 939  1000, guess 969. 6) 970  1000, guess 985. 7) 986  1000, guess 993. 8) 994  1000, guess 997. 9) 998  1000, guess 999. 10) guess 1000.
Mike le
When hiring for a programmer, you do not want someone who "thinks on (their) feet." And the questions are not "on the fly." If someone asks you questions on the fly at an interview, spend your lunchtime applying elsewhere as they have not thought out how to hire the best staff. A good hiring process includes hard questions that offer insight into the applicant and their abilities. Anytime I (or friends) applied for programming jobs, questions like this during the interview were standard. If you could not give a full response (showing the methodology), you did not get the job. While a nice trait to have in a team member, programmers need to be able to code. Bracketing (see Mike's answer, above) is the fastest way. It's boring but it works.
Have you worked as a programmer? le
It IS the binary search; the *minimum* number of guesses would be 1 (if you guessed the correct number right off the bat) and the number of guesses in the average/worst cases would be log N, which is log 1000, ie approximately 10.
hewhojusthadthesamequestion le
Interesting! 22 comments and no correct answer for a pretty simple question (simple if you are not facing interviewer, of course.) Ignoring trivial answer 1 for the question as it stated, for a reformulated question "what is the minimum number of guesses which guaranties you finding the correct number" the correct answer is 9. With 1 guess you can guarantee finding any number from range 13. With 2 guesses  from 17 (First guess is 4, then you have one more guess and 3 numbers to go, if you where not lucky) With 3 guesses  15 With 4  31 ... With N  2^(N+1)1 So, with 9 guesses you can guarantee finding correct number in a range 11023 (and in a range 11000, obviously) BTW, finding what was actually meant when you were asked for something is a crucial part of a programmer's job, so it is better to keep it in mind during an interview. In that case the most probable actual question was "minimum worstcase number" when you were asked for a "minimum number". It's better to ask, not just assume, of course.
Alx le
1000 < 1024 = 2^10; hence within 10 guesses (binary ladder).
Ed C le
The answer to the specific question is  1. 1 is the minimum number of guesses needed. The question is not "What is the min number if you do a binary search correctly and guess wrong each time?". Nor is the question "What is the max number of guesses?". The min number possible is 1 if you guess correctly the first time. Questions like these are generally asked to see the person can weed through the extraneous information and get to the heart of the matter quickly.
JT le
I agree/disagree with both "by <likes it raw" and "by Have you worked as a programmer?" I agree that I think the simplest answer is often overlooked, which is "1", but I also agree that interviewing for a programmer job you would also have to explain your answer and how you came up with that answer. However, I think that all of the other folks that are flaunting their math skills are complicating things, as well. Leave it to programmers to over complicate the simplest solution, which may be what they were looking for in the interview. Do you take an easy problem and make it more complicated than it needs to be or do you try to find the simplest way of resolving the given problem? 2^10 by Ed C seems simple enough for me, but even simpler in my sitting down in a room without a calculator and a manager on the other side of the desk staring me down as I spin my wheels, my thought was to simply reduce the possibilities by 2 with each guess. First guess is 500, if it's lower, next guess is 250 and so on until I isolate on the answer in about 10 guesses. So ultimately, my answer to the person to cover all of my bases would have been. "The most obvious and minimum number that I technically need is 1, if I make a good guess. However, on average I would need a minimum of 10 guesses to pinpoint the number by eliminating half of the options available with each guess." After all the question was how many guesses would it take, which you can come up with a mathematical computation to determine the number of guesses you would need but in practice you would need to actually go about it the way I explained above and that seemed the simplest answer to me.
Nelson Rivera le
JT has it. The minimum number is 1, if you get it right the first time (which you could).
Andrew le
If you use a deterministic algorithm to get to the right answer, then there is no guessing involved, so the answer is "0". If you're asking me what algorithm I would pick, I'd pick a binary search, since I could deduce the right answer in no more than 11 steps.
Steve le
Here is the best answer along with a thorough explanation: http://www.programmerinterview.com/index.php/puzzles/minimumguesses1100/
Mo le
There're quite a few who say that minimum required guesses is either 1 or 2. That would mean the guessed answer is by pure chance and without any logic, which wouldn't be acceptable for a programing job. Like Mike suggested, bracketing method is very logical and anyone can use that method to arrive at that answer as it helps us eliminate big chunk of numbers with every guess
SS le
big O is log2(N) so log2(1000) is 9.97...so the minimum possible answer should be integer which means is rounded to 10. Of course one can guesses up to 999 times to find the correct answer without using binary search.
Ryo le
The question is a bit ambiguous and thus difficult to answer. If they mean the minimum number of guesses that COULD lead to the correct answer the answer is one. However, as a software engineering interview question I'm inclined to believe that it is a test on the applicants knowledge of binary search. As it would take log base 2 N steps to find a solution. As N is the 1000 in this case it would take 10 steps for this scenario.
John Pulford le
Your answer is one. Don't overthink the question. It is possible to guess the right number the first time. So your answer is one.
C W le
Hey, isn't the minimum = 1 maximum= 1000? suppose i guess '1' , o/p= higher then '2', o/p = higher. then '3', o/p = higher. and so on.................. ............................. then '1000' ,0/p = correct'
XYZ le
result ＝ (1000/X1) + (X1/X2)+(X2/X3) + ....+(Xn/Xn+1) restriction: (Xn/Xn+1)<=1, Xn＋1＝range(0，Xn) & Xn is integer
Nergal le
Sound math everyone. A lot of you would be right if the question asked was, "what is the maximum number of guesses required...." But that's not the question here. You could guess the number every time with a maximum of 10 and a minimum of 1 when you are lucky. So pay attention to the question in front of you instead of making it more complicated.
Zzzz le
Or you could follow Josh logic : "The minimum number can not be 1. The question asks what is the minimum if you are given a hint "higher" or "lower." This implies at a minimum 1 hint must be given." But if they said either higher or lower after EACH guess given, then their response would always be either "higher" or "lower", and it would never be "that's correct.," so truly the the implication in this case is that someone is F&*%ing with you.
Utilisateur anonyme le
In general if the given number is N (100 in this case), then the answer should be ceil(log2(N)) i.e. ceil (ln(N)/0.6931) .6931 is ln(2)
Utilisateur anonyme le
I believe the reerence to 'minimum number' is referring to the finding the most efficient algorithm of determining the answer. Using a binary search is the answer based on the responses available (2). If they told you which percent your answer was away from the solution, assuming an integer response, you could have the answer within 3 guesses. The first guess would and response would narrow down the possibilities to 10 or less. The 2nd guess and response would point at the solution making the third guess the answer. As it is, 10 is the correct answer the interviewer was looking for. Imagine instead, the answer is 1000 and guessing: is it 1? Higher 2? Higher ...
Jimmy T le
However, if the number were any of the other numbers you could take the same path and get there in less guesses. It all depends on the number chosen. 500 would be more likely to be chosen in 1 guess because it would be most peoples starting point. 250 and 750 would be next etc...
Utilisateur anonyme le
It's simple just divide the number by 2 or there of to give you a higher or lower response which you can then eliminate the rest of the numbers Guess 1  1000 > 500 Guess 2  500 > 250 Guess 3  250 > 125 Guess 4  125 > 62 Guess 5  62 > 31 Guess 6  31 > 15 Guess 7  15 > 7 Guess 8  7 > 3 Guess 9  3 > 1 Guess 10  2
Leo le
Mike did a good job explaning the Binary Search. I also appreciate "Have you worked as a programmer?" for his valuable comments. I actually ready this interesting article on Binary Search. The actual algorithm is modified to fix a bug (Java 6.0 onwards is fixed). Take a look @ http://googleresearch.blogspot.com/2006/06/extraextrareadallaboutitnearly.html Thanks
Parminder Sandhu le
Great and simple ways to calculate it... Still I think the correct answer is 1. If you are lucky, you will have the exact right number in one guess. That fits the defenition of a minimum. Right? Happy New Year to everybody anyway....
Ronald faas le
The minimum number can not be 1. The question asks what is the minimum if you are given a hint "higher" or "lower." This implies at a minimum 1 hint must be given. The answer is 2. One guess + one hint = 2.
Josh le
You're all wrong (Assuming that the answer isn't 1). It depends on the number and the choices you make when you have to round. When you come to a number like 125 half of it is 62.5 so you have to pick 62 or 63. Because of this it can be anywhere from 9 to 11. Instead of relying on this force guessed point round so that the numbers are always even. If the chosen number is also even you will get it in 9 guess if the number is odd you will get it in 10 guesses. Here is an example using the numbers 189 and 190. 1. 500 4. 188 > 5. 220 < 6. 204 < 7. 196 < 8. 192 < At this point for either 190 or 189 the same path is taken your next guess is 9. 190 10.189
dpdelve le
As far I could understand, since he didn't talk about the number of hints needed but the number of guesses (attempts) needed, I would try this: just one. Just because you could guess it at the first attempt (lucky strike, but who knows?)
Emerson le
You are all wrong. The correct/best answer is 11. Let's assume the question means what is the minimum number of guesses required to be able to pick ANY number in the range 1 to 1000  given that after each guess you will be told  "higher","lower" or "you got it". We all understand that you might guess the number immediately  but that's not the point  because you also might not guess it. So we will evaluate the mimimum number of guesses for the unluckiest guesser using a binary chop approach  which means guess a number right in the middle of the range so that you eliminate approximately half the range each guess. Now here is the key point  it takes one guess to get the right answer  even when you know it is the right answer. So if the question is  how many guesses required to guess a number between 1 and 1  it will take 1 guess (and it will be right). Next consideration  worst case scenario requires that if there are an even number of possible numbers left in the range  you guess the worse half. e.g. Guess number between 1 and 4 (answer is 1): Guess 1: "3" Answer: "Lower" (we have eliminated 4 and 3; 1 and 2 remain) Guess 2: "2" Answer: "Lower" Guess 3: "1" Answer: "You got it". Let's model this: N possible numbers, and our answer is 1. Our guess value is given by (N + 2) / 2 when N is even. Our guess value is given by (N + 1) / 2 when N is odd. N reduces to the number of numbers in the remaining range after each guess. Let's apply this to the problem: Guess 1: (1000 + 2) / 2 = "501" Answer: Lower Guess 2: (501 + 1) / 2 = "251" Answer: Lower Guess 3: (251 + 1) / 2 = "126" Answer: Lower Guess 4: (126 + 2) / 2 = "64" Answer: Lower Guess 5: (64 + 2) / 2 = "33" Answer: Lower Guess 6: (33 + 1) / 2 = "17" Answer: Lower Guess 7: (17 + 1) / 2 = "9" Answer: Lower Guess 8: (9 + 1) / 2 = "5" Answer: Lower Guess 9: (5 + 1) / 2 = "3" Answer: Lower Guess 10: (3 + 1) / 2 = "2" Answer: Lower Guess 11: "1" Answer: You got it. Now Facebook  give me the job  or did I not drink enough Tequila shots while I was doing this?
Ben le
I knew right off that it was binary search, but I couldn't remember the big Oh of that search (its O(log N) ). So I stammered on a bit, because the phrasing "minimum number" had me a bit confused because the minimum number would be 1 guess, but that wasn't the answer she was looking for, she was looking more for the average case I think, which I didn't come up with...
Utilisateur anonyme le
could be wrong but i think yous guys are making this way harder than it actually is...minimum? yea that's 1. you gotta remember..these are questions on the fly, they are only trying to see if you can think on your feet, not do complex mathmatics.
<likes it raw le
log 1000 isn't 10 its 3. Its really log2(1000) which is around 7
Jamie le
Ok, lets solve it this way If I pick 1 by 1 then in worst case I might need 1000 guesses. Now if I move in the interval of 2, I will need 500 + 1 guesses, for 3 I will need 333 + 2 guesses. So we have a pattern here (1000/n) + (n1) = x Now we need to maximize x, so dx/dn = 0 => 1000/n^2 + 1 = 0 so n = sqrt(1000) i.e. n = 31.62 which rounded comes 32 therefore, x = 32 + 31 = 63 So 63 guesses are needed in the worst case.
Dev le