VANS Interview Question
Developer Program EngineersCountry: United States
this Que. was asked in interviewstreet.com ->EKO. I tried to solve it but could not.
Please reply the code with efficient algorithm
Yeah, sounds like a simple backtracking solution is likely to time out. I'm guessing you need to exploit the fact that the order in which items are visited doesn't matter.
Actually the order in which items are visited does matter here.
A particular choice of direction can leave some of the other cells unvisited.
That's not what I meant. I meant that, provided you manage to visit the same cells, the order in which you visit doesn't matter. But yes, the order may affect which cells you are ultimately able to visit.
I'm saying that the fact that we only have to track which combinations of cells can be visited and that we don't have to track all the ways in which identical combinations can be visited may reduce complexity.
its a dynamic problem..
- cobra July 14, 20121. Let the source be grid[0][0] if it is not Zero. then keep on adding max(left,right,up,down) and change the visited grid[i] [j] to zero..so that it cannot be visited again..
2. if you cant move further store the temporary sum say 'temp_sum' in a separate variable say 'max_sum' and start check the other non-zero grid..
3. if the temp_sum becomes greater than max_sum, then max_sum = temp_sum
is my idea right?