Bizarre Tech Job Interview Questions

jiminator

[H]F Junkie
Joined
Feb 2, 2007
Messages
11,618
anything is possible, but for a programming position relying on luck will never get any type of job, especially when 99.9 % of the time the answer will be wrong.

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.
 

jimmyb

2[H]4U
Joined
May 24, 2006
Messages
3,165
What if I guess it on my first try? I only needed 1 guess.
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.
 

nalc

[H]ard|Gawd
Joined
Sep 25, 2010
Messages
1,077
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.
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 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.
 

jimmyb

2[H]4U
Joined
May 24, 2006
Messages
3,165
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.
I didn't claim "guarantee" was in the question. It is however implicit by the phrasing of it.

But you can make a correct guess without eliminating any wrong guesses.
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.
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
You guys are still arguing about that?

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.
 

nalc

[H]ard|Gawd
Joined
Sep 25, 2010
Messages
1,077
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.
 

jimmyb

2[H]4U
Joined
May 24, 2006
Messages
3,165
which would invalidate your answer of 10 as well as my answer of 1.
Actually I never said 10 was the answer. But yes, this would need to be clarified if it wasn't evident for other reasons.
 

Cyrilix

2[H]4U
Joined
Jan 21, 2005
Messages
2,188
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.
 

Blazestorm

Supreme [H]ardness
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).
 

jimmyb

2[H]4U
Joined
May 24, 2006
Messages
3,165
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.
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
As long as it's sorted (which binary search requires anyways) then it doesn't matter. 10 comparisons is the worst case for 1000 items. Because every comparison cuts your data set in half. When they say higher or lower, you throw away half of the items. if the number is 72000 and they are from 1-100,000... you guess 50,000 and they say higher. You throw away 1-50,000... Then guess 75,000 and they say lower, so you guess 67,500 they say higher etc.

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.
 

jimmyb

2[H]4U
Joined
May 24, 2006
Messages
3,165
The question doesn't necessarily frame problem in terms of a software algorithm. A binary search is a good way to solve it in either case.

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.
 

Archmage

2[H]4U
Joined
Jul 13, 2000
Messages
3,023
Note: This post concerns itself primarily with semantics... fair warning.

"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 :)
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
The question doesn't necessarily frame problem in terms of a software algorithm. A binary search is a good way to solve it in either case.

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?
 

nalc

[H]ard|Gawd
Joined
Sep 25, 2010
Messages
1,077
I think my point still stands. There are two ways of viewing this - either you are guessing the correct answer, or eliminating all of the incorrect answers.

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.
 

jiminator

[H]F Junkie
Joined
Feb 2, 2007
Messages
11,618
you are presented with a sheet of this and 9 other pre-interview questions

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
 

jimmyb

2[H]4U
Joined
May 24, 2006
Messages
3,165
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.
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.
 

Archmage

2[H]4U
Joined
Jul 13, 2000
Messages
3,023
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.
 

Archmage

2[H]4U
Joined
Jul 13, 2000
Messages
3,023
Argh - I did this to myself :mad: :

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

outofstep

Weaksauce
Joined
Mar 3, 2005
Messages
125
I was asked about half of these questions during my 1st engineering job interview. It's all interpretive/subjective for this crap. The whole binary search thing would be used in combination with other problems. Answering 1 or answering 10 is simply taken in weight with your other questions.

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

OldSchool

Limp Gawd
Joined
Jul 6, 2010
Messages
477
I really like the first question. The simplest answer as the question is worded is 1, and obviously the more mathematically accurate answer is 10. Getting bogged down with convolution is not necessarily a sign of brilliance, which is something that the engineering type can often suffer from - the inability to see the forest for the trees if you will. Sometimes simplicity can be brilliance as well... ;)
 

Cyrilix

2[H]4U
Joined
Jan 21, 2005
Messages
2,188
I really like the first question. The simplest answer as the question is worded is 1, and obviously the more mathematically accurate answer is 10. Getting bogged down with convolution is not necessarily a sign of brilliance, which is something that the engineering type can often suffer from - the inability to see the forest for the trees if you will. Sometimes simplicity can be brilliance as well... ;)

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