Interview Question
Java DevelopersCountry: India
Interview Type: Written Test
It was not my comment, but the code here:
#include <stdio.h>
int a[100][100];
int dist[100][100];
int n, m;
#define max(a,b) ((a)>(b)?(a):(b))
int DepthSearch(int x, int y)
{
if(dist[y][x])
return dist[y][x];
int mx = 0;
if(x > 0 && a[y][x] > a[y][x-1])
mx = max(DepthSearch(x-1, y), mx);
if(x < n-1 && a[y][x] > a[y][x+1])
mx = max(DepthSearch(x+1, y), mx);
if(y > 0 && a[y][x] > a[y-1][x])
mx = max(DepthSearch(x, y-1), mx);
if(y < m-1 && a[y][x] > a[y+1][x])
mx = max(DepthSearch(x, y+1), mx);
dist[y][x] = mx + 1;
return dist[y][x];
}
int solution()
{
int mx = 0;
for(int i = 0; i < m; ++ i)
for(int j = 0; j < n; ++ j)
mx = max(DepthSearch(j, i), mx);
return mx;
}
int main()
{
int T;
scanf("%d", &T);
for(int t = 0; t < T; ++ t)
{
char name[1000];
scanf("%s%d%d", name, &m, &n);
for(int i = 0; i < m; ++ i)
for(int j = 0; j < n; ++ j)
{
scanf("%d", a[i] + j);
dist[i][j] = 0;
}
printf("%s: %d\n", name, solution());
}
return 0;
}
It is wrong code.Please check for the below matrix:
int a[2][4] = {
3, 4, 5, 6,
10, 9, 8, 7
};
here is the working code.Same technique minor modification
#include <stdio.h>
int a[5][5] = {
7, 2, 3, 4, 5,
36, 37, 38, 34, 6,
33, 44, 46, 40, 7,
24, 43, 42, 41, 8,
35, 32, 47, 30, 9,
};
int dist[100][100];
int n, m;
#define max(a,b) ((a)>(b)?(a):(b))
int DepthSearch(int x, int y)
{
printf("- %d\n", a[x][y]);
printf("%d %d\n", x, y);
int sum=0;
if(dist[x][y])
return dist[x][y];
if(y-1 >= 0 && a[x][y] > a[x][y-1]) {
sum = max(DepthSearch(x, y-1), sum);
}
if(y+1 < n && a[x][y] > a[x][y+1]) {
sum = max(DepthSearch(x, y+1), sum);
}
if(x+1 < m && a[x][y] > a[x+1][y]) {
sum = max(DepthSearch(x+1, y), sum);
}
if(x-1 >= 0 && a[x][y] > a[x-1][y]) {
sum = max(DepthSearch(x-1, y), sum);
}
printf("ended\n");
dist[x][y] = sum+1;
return dist[x][y];
}
int solution()
{
int mx = 0,i, j;
for(i = 0; i < m; ++ i)
for(j = 0; j < n; ++ j)
mx = max(mx, DepthSearch(i, j));
return mx;
}
int main()
{
int i, j;
m=5;
n=5;
for(i = 0; i < m; ++ i)
for(j = 0; j < n; ++ j)
dist[i][j] = 0;
printf("%s: %d\n", "anish", solution());
return 0;
}
Input:
1
Place1 2 4
3 4 5 6
10 9 8 7
Output:
Place1: 8
What wrong?
p.s. My code looks sad after your modifications :(
@volodymyr.zubariev: Your logic is absolutely brilliant.May be my mistake that I didn't get output of the matrix mentioned before.
@volodymyr.zubariev.... your code is working only for static array. not for dynamic array.
can you please try your code with File reading? take 4,5 test cases in file as input.txt with above sample input and write result in output.txt.
Now this is Complicated.
This is clearcut the graph problem. I think people may use Dijkstra's or Prims Algo to rescue .
However, the full fledged working code in interview time is doubtful.
Create a second array that records the longest possible path for each peak. Then work from the lowest peak to the highest peak and check whether going up in any of the four directions can imprive the longest path for the adjacent peaks. The highest number in the new array is the length of the longest path.
This solution requires an additional grid and an auxiliary array for sorting, which makes traversing the grid from the lowest to the highest peak easier.
Example code (in C, sorry):
#define MAX 20
struct Peak {
int h;
int x;
int y;
};
int peak_cmp(const void *a, const void *b)
{
const struct Peak *pa = a;
const struct Peak *pb = b;
return pb->h - pa->h;
}
int longest(int a[MAX][MAX], int width, int height)
{
int l[MAX][MAX] = {{0}};
struct Peak peak[MAX * MAX];
int x, y, n;
int max = 0;
n = 0;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
struct Peak p = {a[y][x], x, y};
peak[n++] = p;
}
}
qsort(peak, n, sizeof(*peak), peak_cmp);
while (n--) {
int h = peak[n].h;
x = peak[n].x;
y = peak[n].y;
l[y][x]++;
if (l[y][x] > max) max = l[y][x];
#define CHECK(C, X, Y) \
if (C && a[Y][X] > h && l[Y][X] < l[y][x]) { \
l[Y][X] = l[y][x]; \
}
CHECK(x, x - 1, y);
CHECK(x + 1 < width, x + 1, y);
CHECK(y, x, y - 1);
CHECK(y + 1 < height, x, y + 1);
}
return max;
}
Create a Directed acyclic graph(you can't get cyclic graph).
a: {b,c,d,e}
Where a is connected to b, c, d and e.
Once you have this graph ready use this technique to find out the maximum distance and return it.
moodle.bracu.ac.bd/pluginfile.php/4784/mod_resource/content/1/longest-path-in-dag.pdf
I guess my algorithm may save some time in solving
Algorithm:
1. Construct the graph with all peaks as nodes and there will be an edge between each adjacent node which is directed from higher to lower peak
2.Get the nodes which has inbound as '0' because that is the starting point that a longest path can start from.
3.Get the nodes which has outbound as '0' because that is the end point that a longest path can end.
4.Now we have only few nodes to consider.
5.Do dfs for all nodes with 0 inbound (of course each dfs will end in 0 outbound vertex).
6.Now the dfs with maximum length will be the solution
My solution will decrease the usage of dfs in the algorithm.
You could convert it to a graph (where each cell is a vertex and its neighbors are only those cells whose value is smaller) and then use a modified Floyd-Warshall algorithm on it: modified, because it would look for max(longestPath(i, j, k), longestPath(i, k+1, k) + longestPath(k+1, j, k)) instead of min(shortestPath(i, j, k), shortestPath(i, k+1, k) + shortestPath(k+1, j, k)).
The comlexity would be O((MxN)^3) where M and N are grid dimensions. I can't think of a more optimized solution at the moment.
You can convert the grid into a directed graph. (Every vertex u will have an edge to its above/down/left/right vertex v, if the value at the vertex v is smaller than the value at vertex u. This will give you a DAG ( there can't be any cycle , think why?).
- graph.algo June 05, 2013So, basically it turns out to be a problem of finding longest path in a DAG. Finding longest path in a normal graph is NP complete, however it can be done in linear time for a DAG.
Here's the algo:
- Get the topological sort of the graph
- start from the node at the end of the topological sort(it won't have any outgoing edge), say the node is w. so the length of longest path starting at w is zero.
- Now look at the second last node , and assign the length of longest path starting at this node (it will be 1 if it has a outgoing edge to the last one or else zero).
- similarly, keep doing this until you reach the first node, and at the end take the max of longest path starting at each node v.
So, the length of longest path starting at v is max(length of longest path starting at u +1), where u are all those nodes such that (v,u) is an edge in the graph.