Subj : Re: Data Structure Problem
To   : comp.programming
From : Gerry Quinn
Date : Mon Aug 08 2005 02:42 pm

In article <1123502711.341939.235380@g43g2000cwa.googlegroups.com>, pp_
5555@yahoo.com says...
> Hi,
> I have a problem in data structures which most of the people find a
> homework but that it is and I am sorry for that.
> i am stuck in this one .Please try to help me , just provide me the
> outline how to analyse this  problem.
>  
>  Question : A man Joe has a habbit of eating pancakes & driving
> bikes.Once he went for outside by his bike,now he is EXACTLY IN THE
> MIDDLE OF A ROAD his stomach is crying for pancakes and also his
> contact lenses are full of dirt.Now HE CANNOT SEE A PANCAKE SHOP UNTILL
> 
> HE REACH THE PANCAKE SHOP EXACTLY BEFIRE IT.
> Now please provide me the algorithm for finding the pancake shop which
> is nearer to JOE & also tell me how can I calculate time and space
> complexity.

Well, the puzzle isn't about data structures as such, but an algorithm 
for finding the nearest shop.

Imagine there's only one shop.  How will he find it?

He'll have to go right for a bit, then turn around and go back to the 
start, then left.

Clearly it would be efficient to multiply the distance he travels in 
each direction by a certain factor each time - calculating the best 
factor might involve calculus, but maybe not.  Doubling it would be a 
reasonable guess.  This is where your time and space complexity come 
in.

But as for a data structure, all you need is to keep control of this 
zig-zagging procedure.  A couple of ints ought to do it!

If there are more than one shops, a little extra check is required when 
one is found.

- Gerry Quinn

.