Your email address:

Powered by FeedBlitz


  • Accident Compensation

  • Save money when shopping online, visit Coupon croc for the latest discount codes and vouchers.

  • See blogs and businesses for USA

  • Southern Utah University

  • Search Now:
    In Association with
Blog powered by Typepad
Member since 02/2004

« Men, Women and Competition | Main | Something Is Rotten In Utah »



It may be too early in the morning to answer this question, but I'd try something like this:

1. Let nf = 1 and nl = 1000000 (subscripts refer to first and last).

2. Look under cans nf and nl. Say the numbers under the cans are yf and yl.

3. Solve n = int[nl+(47000-yl)*(nl-nf)/(yl-yf)].

4. Look under cans n-1, n and n+1. If y[n-1] .LT. 47000, y[n+1] .GT. 47000 and yn .NE. 47000 then 47000 isn't there; stop. If yn = 47000, then it is there; stop. Otherwise, if yn .GT. 47000, let nf = 1 and nl = n; go to step 2. If yn .LT. 47000, let nf = n and nl = 1000000; go to step 2.

I had to use the old FORTRAN codes for less than and greater than because those symbols were not being printed for some reason. So how'd I do?


Of course ... I'm not an interviewer ... but if I were I probably wouldn't be happy with this answer.

It isn't that it wouldn't work, but rather how you would actually go about performing step 4. Even if you know n from step 3, how are you going to find the n'th can? Count them? How long would that take?


If we are to imagine that someone has lined up one million cans, then we have already stepped outside reality. So in that spirit, my answer is that I tell a pixie which can I want. She flies down the line at supersonic speed, counting the cans she passes, and stops at the number I told her.

Failing that, since the line is miles long (unless the cans are microscopic) I could measure the width of one can and figure out how far I need to drive my car to get to the right one.


Hope I didn't offend you ...

I believe the sort of answer they are looking for is something that divides the set in two at each step, isolating the can in question in ever smaller subsets. Such a method would have a workload proportional to the log of the number of cans.

Once you are in the set of algorithms that are that efficient, they are probably looking for something that doesn't require counting, or the evaluation of a formula (as yours did). It helps, but only moderately, to have some rule about where to choose the point of division - and I'm not sure that a formula is the sort of thing they are looking for in an interview.


It's a simple case of binary sort - O(logn)

Dave Tufte

For you and me and my former student, yes.

For many others, it seems not.

cheap jerseys

concerning 12L y Three.5W y 7H and has




Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.


Post a comment

Your Information

(Name is required. Email address will not be displayed with the comment.)

Recent Reading

  • The Earthsea Cycle
  • From Archetype to Zeitgeist

Non-Economics Blogroll

Gone but not Forgotten


Movie Rating