Comment by c0ff | Hacker News Reader

Comment by c0ff | Hacker News Reader

Parent Full thread

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.

Given that is a theoretical question that you are attempting to fit into an actual algorithm to ostensibly solve a real problem, doesn't the actual performance of the algorithm matter? I can see that within the context of theory of computer science there may not be a difference between the speed of the two algorithms, since both are "asymptotically optimal" (a term I'm not sure I entirely grok), yet within virtually any defined set of random numbers less than infinity the algorithm I provided will perform substantially faster.

I suppose I'm at a loss for words, since as a seasoned software developer without a deep background in theoretical computer science, it seems that I am being told to disregard my intuition based on experience in favor of a theoretical model that seems to ignore actual problem sets. Am I missing something?

I made a python script to time the different approaches:

https://gist.github.com/3839551

AFAICT, the parent and the interviewer is right because both methods run in roughly the same time because the time of the binary search is orders of magnitude greater than the upper bound finding part. I might have made one or more mistakes though.

If I have time later today I'll extend your snippet, but my inclination is that the differences in speed become apparent only with very large numbers. I still suspect my algorithm is about 40-50% faster if you start with a googol.

It seems that the problem involves two parts: 1) To find an upper bound 2) Then divide the remaining region in halves until the number is found.

The first observation that I have is that given that the secret number s is chosen, the first step can be completed arbitrarily quickly. One could use a function that rises arbitrarily fast. Imagine for example the function taking k to the Ackerman function A(2,2,k). That rises so fast it's incomprehensible, but really one could easily produce a function which rises faster still (the algorithm that picks s first!). The problem is, though, of how fast a fixed algorithm is for random s. If s is truly chosen at random from the positive integers, this leads to problems. Fix your putative algorithm. Suppose for the moment that it starts at 0 (it is not going to matter where it starts) What is the probability that the kth number that your function spits out is less than a random integer? 100% After all, how many integers are greater than any given integer?

Therefore, no growth function is any better on average at finding the upper bound than any other. Therefore step 1) is an insoluble problem. The problem should have been specified in some other way in order for it to make sense.

However, the second step involves log_2(n) time (in the worst-case-scenario and still O(log n) in general) where n is the upper bound --the output of step 1-- which means that the time to complete the algorithm is (Time of step 1 to find n) + O(log n). IF the problem made sense and it was the case that step 1) were soluble, then it would matter how fast step 1 is countered by the degree to which step 1 tends to overshoot the secret number --because overshooting by k has the penalty of log(k) extra operations.

Is there are framework in which question 1 makes sense? It would make sense if there were a given probability distribution on the integers (a function on the positive integers whose sum over all integers = 1, for example choose the function f(n) = 6/(n^2 * pi^2)) A probability distribution gives you a way of answering the question: "what proportion of the positive integers are greater than k?"

Excellent response. I think the framing element that was missing is if the random numbers were truly random.

This was my conclusion, that although the two approaches had the same average big O time, my intuition said it was somewhat faster to start from some number larger than 0.

In retrospect, I might have mentioned this and then gave the interviewer's preferred answer in code, just to keep things simpler.

My intuition says that they should almost always run at about the same time if you don't know anything about the distribution of guesses. Your algorithm has the advantage that it will find an upper bound for the number much faster than the interviewer's algorithm. HOWEVER, having found that upper bound, your algorithm will probably be much farther away from the actual number than the interviewer's, so you have to do that much more narrowing down. What it comes down to is being lucky that you're close to the number in your initial guess, otherwise, you're still talking logarithmic time to either find an upper bound or (in your case) lower bound for the number.

Reply on news.ycombinator.com