Can you write some pseudo-code for your algorithm?
I think it has a problem with how-much-time-to-wait-in-one-lane.
For example, there are two lanes and cars are coming as:
lane1 10 5 4 3 2 1
lane2 9 6 3
So, the times when the car is not there will be:
lane1 9 8 7 6
lane2 10 8 7 5 4 2 1
It is indeed an elegant interview question with respect to hiring for
designing the systems.It was asked when I was interviewed for the final
rounds of on-site interview at Google.
On Thu, Jul 15, 2010 at 11:47 PM, Tech Id tech.login@gmail.com wrote:
Hi Ashish,
Your algo does not have a
it does have, have been thinking on this since y'day and it will still work
with a little modification
in case there is a path, it indeed covers move back possibilities with two
adjacent lane timings2
alternatively, if frog moves back ,based on current time, only possible
entries after the
An inefficient but working method is the brute force one.
Do a recursive test for all the cases possible and if you
find one which helps the frog cross the road, then that is it.
Let int car_times[numLanes] store the time each car will take to reach
the path where the frog is crossing the road.
http://code.google.com/p/frogger-game/source/browse/trunk/
can it be interview question??
the frong will wait and this would vary at run time, the car_times is
storing just one value, multiple cars can come in a lane so it should be
hash map
one thought: for each lane we know when the car would
Hi Ashish,
Your algo does not have a chance for jump_back.
This may be required for certain cases, especially when multiple cars
are running on one lane.
My solution was for one car on one lane, hence car_times[i] gives the
car in i-th lane will take to hit the path frog is trying to cross.
It