Interview Question for Software Engineer at Facebook:

Jan 19, 2010

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...

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.

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

they were asking for the minimum number of guesses required to solve the problem in the worst case

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.

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.

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?)

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.

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.

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

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

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....

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.

This is simply a question of remembering what you were taught in your algorithm class. The best case complexity is O(1), or, "1 if you're lucky", but you never, ever assess any requirement by luck.

Both the average and worst case complexity is O(Log2 n), and in practice, an estimate of n is what you're given, and it's your job to deduce the best algorithm for the process by assessing both the complexity of the search function AND the performance of each iteration. In real life the answer is usually "I'll look it up".

For the question above, the correct answer is the complexity function. The resulting value is irrelevant, although in this case the required number of iterations for n=1000 is 10, as pointed out. A quick brain will evaluate the value by iteration, but the function itself is the answer most appreciated, if you're being interviewed for a job as a programmer, engineer or even an architect.

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.

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 <
2. 250 <
3. 126 >
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

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...

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

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.

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

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)

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
...

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.

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.

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.

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.

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

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?

Here is the best answer along with a thorough explanation:

http://www.programmerinterview.com/index.php/puzzles/minimum-guesses-1-100/

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.