## Groupon Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Assuming no diagonal movement, and Length is accumulated on each step, recursively:
Length(i, j) = min( Length(i-1, j) + Value[i-1, j],
Length(i+1, j) + Value[i+1, j],
Length(i, j-1) + Value[i, j-1],
Length(i, j+1) + Value[i, j+1] );

To optimize, we can borrow from Dynamic programming and store calculated Length(i, j). So you look up at the beginning of the function and return, or store the calculated length at the end:

Length(i, j)
if (i, j) is border, return 0
if L[i, j] is stored, return L[i, j]
int length = min ( ... as above ... )
L[i,j] = length
return length

Comment hidden because of low score. Click to expand.
1
of 1 vote

variation of flood fill algorithm

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is diagonal movement allowed ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

int ShortestPath(int **mat, int m, int n, int currposx, int currposy)
{
if(currposx < 0 || currposy < 0 || cussposx >= m || currposy >= n)
return;
if(currposx == m-1 || cussposy == n-1 || currposx == 0 || cussposy == 0)
return mat[currposz, currposy];
else
{
return min((shortestPath(mat, m, n, currposx+1, currposy),
(shortestPath(mat, m, n, currposx-1, currposy),
(shortestPath(mat, m, n, currposx, currposy+1),
(shortestPath(mat, m, n, currposx, currposy-1)) + mat[currposx,currposy];
}
}

Please let me know if I am doing something wrong here

Comment hidden because of low score. Click to expand.
0

Wouldn't it recursively call the function with the same values.
Let currposx = 2, currposy = 2.
The call results in a call to the function with values 3,2. This function will again make a call to the function with values 2,2. It would be an infinite loop.

Comment hidden because of low score. Click to expand.
0

This looks a lot like DFS. Would this not be possible by DFS where the termination of a DFS path can be set to the boundary of the grid?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.