4 ms·

It's a binary search in infinite space. His solution expands the problem area until the number is in the space and then shrinks the problem area until it finds

It's a binary search in infinite space. His solution expands the problem area until the number is in the space and then shrinks the problem area until it finds the number. A better solution is to pick an arbitrarily large number and only expand if you have to--otherwise you're shrinking from the very beginning. That's how I would have answered the question, anyway. But yes, I've dealt with interviewers like this--typically it's because they don't understand the subject matter well enough to evaluate or accept an answer they didn't prepare for.

teraflop 14y ago
I disagree that that solution is unequivocally better. It depends on the distribution of the input data; if the expected value of the number is small, then you're better off starting at zero than dramatically overestimating. Of course, either way the algorithm runs in O(log n) time.
- Jd 14y ago
  Within the context of the interview question, the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. This is the error that my interviewer made. He was trained to deal with things within the context of situations closer to real life rather than the theoretical box he had established for the interviewing situation. As for my case, I did attempt to start at an arbitrarily large number (but he wouldn't let me), and then went up exponentially (i.e. x = x * x), bi-secting the space once the upper-bound was found and solving from there. My interviewer was sadly not that bright and didn't understand my solution, forcing me to re-write it -- incidentally, lecturing me on how wonderful O(log n) is along the way.
  - teraflop 14y ago
    > the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. Closer to 0 than what? Infinity? By any reasonable definition, every integer is closer to 0 than infinity. I think the problem as stated is underspecified; I disagree that increasing "exponentially" (the solution your interviewer described would increase exponentially; your version is doubly exponential, I think) is always faster. Both versions have the same worst-case running time, and if you want to talk about expected running time you need to make assumptions about the data distribution. As a counterexample, if you start with an initial guess of 2 and keep squaring, but the true number is 2^1025, then you end up doing much more work than if you had doubled instead of squaring. I can certainly agree with you that lecturing in an interview is unproductive. Not only is it understandably off-putting, but it doesn't give the interviewer any additional input to the hiring decision and therefore is a waste of everyone's time. (Unless one of the job requirements is coping well with being lectured to, I guess.)
    - Jd 14y ago
      > By any reasonable definition, every integer is closer to 0 than infinity. Perhaps, but originally we weren't discussing 0, we are starting with an arbitrarily large number. This problem is exacerbated when you say: > I disagree that increasing "exponentially"... is always faster ... Both versions have the same worst-case running time Worst case, sure, but how do you compute average? You could take a selection of n number of integers from 0 to infinity and the number of guesses until you found the correct answer, but of course you can't do this because you can't easily get a random number to test with that is between 0 and infinity. That said, it is fairly clear that x * x is faster than 2x is faster than x+1, but you can only prove this to be true once you pick an arbitrary limit less than infinity -- and the benefits of the better algorithm are only evident as you approach infinity. Seems like a catch 22. Perhaps there is some expert in set theory as applied within computer science that can provide the appropriate formal context for determining the better algorithm in this context. As for O notation, it is an interesting tool but one that has no application within any realm of actual programming in which I have worked, and I have never bothered to learn it simply to dazzle people in algorithm-based interviews (perhaps because I do more nuts and bolts type work rather than optimization).
      - c0ff 14y ago
        From the perspective of theoretical computer science, the interviewer was correct. I'll try to sketch out why. ------------------ 1. In the initial probing for the upper bound, there is no point to grow faster than 2x each time If we double the probe each time, we'll find the upper bound in O(log N) time. Then, we'll need O(log N) additional time to find the real answer. That makes the entire algorithm O(log N). Suppose instead, in the initial probing we grow the bound faster, say by squaring each time. We'll find the upper bound faster, but we'll still need additional O(log N) time to find the real answer. So, we didn't really make the algorithm (asymptotically) faster - it is still O(log N). (I glossed over some details in the explanation, but even if you work out the math exactly - which is not that hard to do - the conclusion holds.) ------------------ 2. There is no point starting from a number greater than 1 There is no way to pick a "good" starting number - should it be 1,000? 1,000,000,000? 10^100? (10^100)^100? You might as well start from 1. That way, you guarantee that you'll find small numbers fast and large numbers still in an asymptotically optimal time. ------------------ As someone with fairly strong theoretical computer science backgound, I can see the intended meaning behind the interviewer's question and answer. But, it is a theoretical question. There definitely are a lot of highly valuable software developers out there who couldn't answer it.

teraflop 14y ago

I disagree that that solution is unequivocally better. It depends on the distribution of the input data; if the expected value of the number is small, then you're better off starting at zero than dramatically overestimating. Of course, either way the algorithm runs in O(log n) time.

Jd 14y ago
Within the context of the interview question, the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. This is the error that my interviewer made. He was trained to deal with things within the context of situations closer to real life rather than the theoretical box he had established for the interviewing situation. As for my case, I did attempt to start at an arbitrarily large number (but he wouldn't let me), and then went up exponentially (i.e. x = x * x), bi-secting the space once the upper-bound was found and solving from there. My interviewer was sadly not that bright and didn't understand my solution, forcing me to re-write it -- incidentally, lecturing me on how wonderful O(log n) is along the way.
- teraflop 14y ago
  > the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. Closer to 0 than what? Infinity? By any reasonable definition, every integer is closer to 0 than infinity. I think the problem as stated is underspecified; I disagree that increasing "exponentially" (the solution your interviewer described would increase exponentially; your version is doubly exponential, I think) is always faster. Both versions have the same worst-case running time, and if you want to talk about expected running time you need to make assumptions about the data distribution. As a counterexample, if you start with an initial guess of 2 and keep squaring, but the true number is 2^1025, then you end up doing much more work than if you had doubled instead of squaring. I can certainly agree with you that lecturing in an interview is unproductive. Not only is it understandably off-putting, but it doesn't give the interviewer any additional input to the hiring decision and therefore is a waste of everyone's time. (Unless one of the job requirements is coping well with being lectured to, I guess.)
  - Jd 14y ago
    > By any reasonable definition, every integer is closer to 0 than infinity. Perhaps, but originally we weren't discussing 0, we are starting with an arbitrarily large number. This problem is exacerbated when you say: > I disagree that increasing "exponentially"... is always faster ... Both versions have the same worst-case running time Worst case, sure, but how do you compute average? You could take a selection of n number of integers from 0 to infinity and the number of guesses until you found the correct answer, but of course you can't do this because you can't easily get a random number to test with that is between 0 and infinity. That said, it is fairly clear that x * x is faster than 2x is faster than x+1, but you can only prove this to be true once you pick an arbitrary limit less than infinity -- and the benefits of the better algorithm are only evident as you approach infinity. Seems like a catch 22. Perhaps there is some expert in set theory as applied within computer science that can provide the appropriate formal context for determining the better algorithm in this context. As for O notation, it is an interesting tool but one that has no application within any realm of actual programming in which I have worked, and I have never bothered to learn it simply to dazzle people in algorithm-based interviews (perhaps because I do more nuts and bolts type work rather than optimization).
    - c0ff 14y ago
      From the perspective of theoretical computer science, the interviewer was correct. I'll try to sketch out why. ------------------ 1. In the initial probing for the upper bound, there is no point to grow faster than 2x each time If we double the probe each time, we'll find the upper bound in O(log N) time. Then, we'll need O(log N) additional time to find the real answer. That makes the entire algorithm O(log N). Suppose instead, in the initial probing we grow the bound faster, say by squaring each time. We'll find the upper bound faster, but we'll still need additional O(log N) time to find the real answer. So, we didn't really make the algorithm (asymptotically) faster - it is still O(log N). (I glossed over some details in the explanation, but even if you work out the math exactly - which is not that hard to do - the conclusion holds.) ------------------ 2. There is no point starting from a number greater than 1 There is no way to pick a "good" starting number - should it be 1,000? 1,000,000,000? 10^100? (10^100)^100? You might as well start from 1. That way, you guarantee that you'll find small numbers fast and large numbers still in an asymptotically optimal time. ------------------ As someone with fairly strong theoretical computer science backgound, I can see the intended meaning behind the interviewer's question and answer. But, it is a theoretical question. There definitely are a lot of highly valuable software developers out there who couldn't answer it.