That is like writing a comparison function where it always returns the first value as being the smallest. it WILL work half of the time. The rest of the time the programmer is an idiot.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter MajorDomo
- Start date

That is like writing a comparison function where it always returns the first value as being the smallest. it WILL work half of the time. The rest of the time the programmer is an idiot.

You cannot guarantee a correct guess. Therefore to find "a specific number" you need more than one guess. Number is predicated by an indefinite article; it is arbitrary and refers to the entire set of possible numbers.What if I guess it on my first try? I only needed 1 guess.

You're absolutely right that I can't guarantee a correct guess. Please point out where the word" guarantee" is located in the original question and ill gladly eat my words.You cannot guarantee a correct guess. Therefore to find "a specific number" you need more than one guess. Number is predicated by an indefinite article; it is arbitrary and refers to the entire set of possible numbers.

The only way to guarantee a correct guess is to eliminate the 999 wrong guesses, which requires a minimum of 10 steps. But you can make a correct guess without eliminating any wrong guesses.

I didn't claim "guarantee" was in the question. It is however implicit by the phrasing of it.You're absolutely right that I can't guarantee a correct guess. Please point out where the word" guarantee" is located in the original question and ill gladly eat my words.

The question specifically uses the word "needed" to find an arbitrary number. The question doesn't even require that the number be selected by the asker before the guessing begins, and therefore the asker can guarantee that it will never be on the first guess by simply saying lower or higher.But you can make a correct guess without eliminating any wrong guesses.

- Joined
- Jan 17, 2007

- Messages
- 6,940

This is a question that's obviously referring to binary searching, and the worst case scenario. Yes you can get it in 1 guess with most binary search algorithms that would be the middle of the set. Algorithm analysis is usually referring to the worst case scenario, and with binary searches it's log2(N).. so for ~1000 items (1024 or 2^10) there are 10 comparisons at worst... if it was a million items, only 20 comparisons at worst, and a billion items would be 30 comparisons at worst... 1 comparison at best... average case is still roughly the same as worst case because 50% of the items will take 30 comparisons, the other 50% take less. The point is to understand the worst possible performance of algorithms so that you know where the bottlenecks in your code could be.

Whoever is still arguing that the answer is 1 guess can give up... maybe the question was worded oddly but most of these look like they're for software development anyways and anyone competent in that field can probably see what the question is really looking for.

The question doesn't even require that the number be selected by the asker before the guessing begins, and therefore the asker can guarantee that it will never be on the first guess by simply saying lower or higher.

It also doesn't require the number to be an integer, so by the reasoning that the number doesn't have to be selected by the asker before the guessing begins, there is no solution as the asker could select an irrational number. If its possible for the asker to guarantee that it will never be on the first guess, the asker can also guarantee that it will never be guessed, which would invalidate your answer of 10 as well as my answer of 1.

You don't even know this is possible. The responder could simply say higher or lower after every single first guess.Yes you can get it in 1 guess [...]

Actually I never said 10 was the answer. But yes, this would need to be clarified if it wasn't evident for other reasons.which would invalidate your answer of 10 as well as my answer of 1.

Nope. Specific number means that there's only one correct number out of 1000 numbers. Need means that you absolutely cannot guess the correct answer with less than that number of guesses. You say that 10 guesses are needed. What if I guess it on my first try? I only needed 1 guess. Saying that you need 10 means that it is not possible to do with less than 10, which is clearly false.

No, nalc, you're just too stupid to recognize an actual open-thought question like "how would you move mount fuji?" and think every question being asked is always like that.

- Joined
- Jan 17, 2007

- Messages
- 6,940

You don't even know this is possible. The responder could simply say higher or lower after every single first guess.

You actually can know.

After 10 comparisons it's rather found or it doesn't exist in the set... this is a simple programming related question...

And nalc, it doesn't matter if it's not an integer, or if it's irrational, or if it's a string, or a banana... this question is referring to a binary search which works on data sets that have random access using indexes (which should be integers).

You actually can know.

I was responding to the claim that it is possible to get the correct answer in 1 guess. You can't know this is possible because you don't know the nature of how the numbers are being picked.

If we assume the question is referring to the integers from 1 to 1000, then yes, we know we can get it in no more than 10 guesses, regardless of how the number is picked.

- Joined
- Jan 17, 2007

- Messages
- 6,940

I still don't know what the argument is... if it exists in the set, it can be found in 1-10 comparisons. If it doesn't exist in the set, you know after 10 comparisons. This is the worst case and that's what the question is really asking.

If you want to get really pedantic, you need to provide an optimality proof along with your solution to show that it is not possible to do it any faster.

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

Thank you for giving us the exact question.

I agree that the words "needed," "specific," and "find" are limiting, and thus:

We can reasonably assume that they'd have been satisfied with anyone who simply solved the problem.

But they STILL needed a stipulation along the lines of, "... required to repeatedly (systematically, without fail) ascertain (with certainty)..." or, in some manner, to have excluded random guessing and instead ask of you the algorithmic answer. They may have instead asked for a general formula given variable constraints, if they really wanted to test the applicant's knowledge.

Furthermore, we are given a hint AFTER each INCORRECT guess... not "for each guess." That remains true regardless of the intent of the question. The question is simply poorly worded.

Consider that even using the binary search, the possibility arises that the algorithm "guesses" the correct answer before all trials have completed. They need to account for this possibility when wording the question.

Furthermore, the last "guess" is NOT a guess at all. After 9 "guesses," the applicant has "FOUND" the "specific number." For Instance, if the "hint" is "lower" every time, we have: (500, 250, 128, 64, 32, 16, 8, 4, 2), and we "find" 1.

THIS is the reason I never actually said the answer was "10;" I instead referred to "solving the problem," but I figure it's constructive at this point. And YES - I immediately thought about ALL of this...probably because I have a lot of test-taking experience.

What we REALLY should know:

Whether or not the intent is implicit IS relevant - This question is informal, and thus it's up to the applicant to seek clarification (which may be MORE TACTFUL than to provide both answers).

The question doesn't seem to explicitly disallow guessing - it encourages it with the use of the word...

That's my opinion - others are welcome, but it's also my opinion that I've spent too much time on this silly question. I'll check back later to see if someone convincingly disagrees, because that engenders a learning experience, but I'll go uh... enjoy dinner with the family now - Steak and vegetables...yay

- Joined
- Jan 17, 2007

- Messages
- 6,940

If you want to get really pedantic, you need to provide an optimality proof along with your solution to show that it is not possible to do it any faster.

I guess during the interview you could ask some clarifying questions if you really wanted to...

And to Archmage, yes the final "guess" is still considered a "guess" because you still had to check to see if it was 1... it's still the same amount of work to see if you found the right item or not... 10 comparisons.

Also, whats the worst case for finding an item in a binary search tree?

From what I gather about this 'binary search' (I have no computer science background), it eliminates incorrect answers, thus splitting the domain of potential answers in half after every iteration of the process.

First time around, you eliminate 500, leaving 500. Next time, you eliminate 250, leaving 250. Third time, eliminate 125, leaving 125, and so on, until you are left with 1.

That undoubtedly has the highest probability of correctly guessing the answer, with a 100% probable answer after the 9th iteration.

However, there still exists a 0.1% possibility of a correct first guess. And a 0.2 possibility of a correct second guess. And a 0.4% possibility of a correct third guess, and so on, until you have a 100% possibility of a correct tenth guess.

But, to say that the minimum number of guesses required is 10 is incorrect.

Taking the cumulative probability, and using the most systematic and efficient process, you have the following:

0% chance of guessing it without making any guesses

0.1% chance of guessing it on the first try

0.3% chance of guessing it on or before the second try

0.7% chance of guessing it on or before the third try

1.5% chance of guessing it on or before the fourth try

3.1% chance of guessing it on or before the fifth try

6.3% chance of guessing it on or before the sixth try

12.7% chance of guessing it on or before the seventh try

25.5% chance of guessing it on or before the eighth try

51.1% chance of guessing it on or before the ninth try

100% chance of guessing it on or before the tenth try

Thus, any number greater than 1 is possible.

your options:

1) say fuck it, I don't need this job that much - may work for you, others not so much

- no job

2) go and query someone about the exact meaning of each question

- wtf? he needs his hand held to answer a few questions? no initiative? - no job

3) write the answer "1" specifying it is the minimum number of guesses

- guy is a moron - no job

4) write "10" and possibly the reasoning behind the answer

- finally someone with a brain, hire this person if other things check out

Even in a binary search you can't know those probabilities of success since you don't know the pdf of the number you are guessing or if it can even be modelled with traditional methods like that, such as if the number is not predetermined - the question merely states that you need to find "a specific number". Assuming integers we don't even know if it is possible to get it before the 10th guess, but we do know that we can find it before the 11th.However, there still exists a 0.1% possibility of a correct first guess. And a 0.2 possibility of a correct second guess. And a 0.4% possibility of a correct third guess, and so on, until you have a 100% possibility of a correct tenth guess.

But, to say that the minimum number of guesses required is 10 is incorrect.

And to Archmage, yes the final "guess" is still considered a "guess" because you still had to check to see if it was 1... it's still the same amount of work to see if you found the right item or not... 10 comparisons.

Definitely valid if the number does not belong to the set of integers 1-1000, or if somehow the selected number has changed, thus invalidating the hints altogether. - good point.

Whether or not the number is randomly pre-determined or possibly re-selected after each iteration is important...

I would have expected a question such as this to clearly identify the set, that the number in question belongs to the set, and how the number will be determined, or I would have begun my response with a list of corresponding assumptions, "Given that...[the above]..." - essentially re-writing the question for them.

Anyone qualified for the job will have seen mathematical questions worded in this manner... clearly defined. This question simply is not.

For some reason I was under the impression that this was an oral interview. No matter - I don't believe that seeking clarification will work against the applicant.

That question came from Facebook - a guy from my high school is now working for FB. He would have sought clarification or provided excessive explication of his own, or else it would have driven him insane. If written, I think the qualified applicants would phrase the answer with sufficient mathematical rigor so as to avoid being incorrect, though it would depend on their personality to some degree.

I think you've all covered the question in sufficient detail... good exercise.

Obviously if the hints are invalidated, and the selected number keeps changing, then the process does not apply. If the selected number changes after each iteration, then it must NOT invalidate the hints, or else the question is pointless.

OK - I'm done... it's done... we're done... I'm tired...

The only people getting the wrong answer are the people saying answering 1 or answering 10 will get you hired or fired.

Actually, replying with 1 will generally be okay. They will simply tell you: "That's a reasonable answer, but can you think of another one, given that we're emphasizing..."

Happened to me many times before. Word questions almost always have more than one answer, but they are still looking for the answer they want, and will often give you hints if you haven't hit that one yet.