## Support

• Accident Compensation

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

•  Search Now:

## Archives

Member since 02/2004

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)

For you and me and my former student, yes.

For many others, it seems not.

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

The comments to this entry are closed.

• The Earthsea Cycle
• From Archetype to Zeitgeist