CareerCup

the question seems too difficult to me..would someone like explaining the working solution rather than putting such big chunk of codes which seem to be in-comprehensible to me/us! thank you.

Jack can you please explain the solution you gave.
(BTW...good luck to you....hope you make it.)

He once said, you don't have to use "this func." He pointed out like 1/2 through the interview that "this" function is an initialization function that calls a recursive function. So I was like, oh good, that makes things much easier and told me my initialiation function was perfect. He was holding back some things he wanted to see until 1/2 through the interview. He told me ahead of time, that this interview was to test my coding ability.

These were the interfaces:
BOOL doRiver(BOOL river[], int len);
BOOL doSubRiver(BOOL river[], int pos, int speed, int len);

BOOL doRiver(BOOL[] river, int len)
{
if(river[0]==false)return false;
doSubRiver(river,0,0,7);
}

BOOL doSubRiver(BOOL river[], int pos, int speed, int len)
{
if(river[pos]==false)return false;

return dSR(river,pos+1,speed-1,len-1)|| dSR(river,pos-1,speed-1,len-1) || dSR(river,pos,speed,len);

}

He said to find all combinations and see if it's possible for the grasshopper to cross the river, when the river is given as input to the function.

I did quite a bit of math/logic though before the coding so that's why my code seems short.

The last arg of the last func call, was len-1.

actually, the first func call should be this...

doSubRiver(river,0,1,7);

Jack, shouldn't this function return TRUE somewhere?

Shouldn't the correct code be something like below? And also, You don't have a base case. This function doesn't terminate.

BOOL doSubRiver(BOOL river[], int pos, int speed, int len)
{
if (river[pos]==false) return false;

if(pos == len) return (river[pos]

if (! dSR(river,pos+1,speed-1,len)|| !dSR(river,pos-1,speed-1,len) || !dSR(river,pos,speed,len))

return false;

return true;

}

Why the 'speed' parameter is left there but never checked in the function?

I guess we need to do sth more to handle the 'speed'.

Also when you add pos + speed we need to be checing array bounds to see pos + speed is within len

bool valid(bool[] interval,int index,int len)
{
if (index >= len)
return false;

return interval[index];

}

bool cross(bool[] intervals,int currInt,int currSpeed,int len)
{
// assuming len + 1 is the other end...len being the last stone
if (currInt == len)
return true;

if (currInt > len + 1 || currInt < 0)
return false;

if (currSpeed <= 0)
return false;

return ( valid(intervals, currInt + currSpeed, len) && cross(intervals,currInt+currSpeed,currSpeed,len) ||
valid(intervals, currInt + currSpeed + 1, len) && cross(intervals,currInt+currSpeed + 1,currSpeed + 1,len) ||
valid(intervals, currInt + currSpeed - 1, len) &&cross(intervals,currInt+ currSpeed - 1,currSpeed -1, len) );

}

bool doCross(bool[] intervals,int currInt,int currSpeed,int len)
{
if (intervals[0] == false)
return false;

// to get rid of tricky 0 speed valid case to start with
return cross(interval,1,1,10);
}

what a difficult question

Slightly different solution (I think), but one that is very condusive to commenting. Please let me know if I've made a mistake.

bool
doRiver(BOOl river[], int len)
{
        if (len == 0)
        {
                return true; // Nothing to cross.
        }
        if (river[0])
        {
                return doSubRiver(river, 0, 1, len); // Got to first stone.
        }
        return false; // First stone is too far away.
}

bool
doSubRiver(BOOL river[], int pos, int speed, int len)
{
        // Calculate target position.
        int target = pos + speed;

        if (target >= len)
        {
                return true; // Landed on or overshot far bank.
        }

        if (target + 1 == len)
        {
                return true; // Could accelerate to far bank.
        }

        if (river[target + 1])
        {
                // Could accelerate to next stone, so increase speed
                // and set position to new target.
                return doSubRiver(speed + 1, target + 1, river, len);
        }

        if (river[target])
        {
                // Current speed is ok, so move to target.
                return doSubRiver(speed, target, river, len);
        }

        if (speed - 1 == 0)
        {
                // Cannot decelarate since we would cease to move!
                return false;
        }

        if (river[target - 1])
        {
                // Can decelerate to next stone, so decrease speed and
                // set position of new target.
                return doSubRiver(speed - 1, target - 1, river, len);
        }

        // No stone is within reach.
        return false;
}

Shouldn't the declaration of your function be doSubRiver(speed, pos, river, len) , as per the recursive calls in your function.