## Questions d'entretien

Entretien pour Software Engineer

-

# Given 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épondre

## Réponses aux questions d'entretien

32 réponse(s)

26

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

15

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

10

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.

3

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 1-3. With 2 guesses - from 1-7 (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 1-1023 (and in a range 1-1000, 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 worst-case number" when you were asked for a "minimum number". It's better to ask, not just assume, of course.

Alx le

2

1000 < 1024 = 2^10; hence within 10 guesses (binary ladder).

Ed C le

2

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

1

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

1

JT has it. The minimum number is 1, if you get it right the first time (which you could).

Andrew le

1

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

1

Here is the best answer along with a thorough explanation: http://www.programmerinterview.com/index.php/puzzles/minimum-guesses-1-100/

Mo le

1

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

0

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

0

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

0

Your answer is one. Don't over-think the question. It is possible to guess the right number the first time. So your answer is one.

C W le

0

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

0

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

0

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

0

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

0

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

0

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

0

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

0

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

0

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/extra-extra-read-all-about-it-nearly.html Thanks

Parminder Sandhu le

0

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

0

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

0

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

1

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

0

Ben le

2

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

3

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.

&lt;---likes it raw le

2

log 1000 isn't 10 its 3. Its really log2(1000) which is around 7

Jamie le

1

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) + (n-1) = 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

## Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.