## Interview Question for Java Developers

Country: India
Interview Type: Written Test

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

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?).

So, 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.

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

@graph.algo: very good approach.

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

DFS algorithm can be used to find the longest path here.

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

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;
}``````

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

It is wrong code.Please check for the below matrix:

``````int a[2][4] = {
3, 4, 5, 6,
10, 9, 8, 7
};``````

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

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;
}``````

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

Input:
1
Place1 2 4
3 4 5 6
10 9 8 7

Output:
Place1: 8

What wrong?

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

@volodymyr.zubariev: Your logic is absolutely brilliant.May be my mistake that I didn't get output of the matrix mentioned before.

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

@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.

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

@rake.muppa: that is very trivial to implement, is not it?

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

@volodymyr.zubariev: Thanks you so much for your logic.... I did it in java with dynamic data...

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

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.

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

@hprem991: Dijkstra's won't work as you don't have a destination node.I don't know about prims algo.

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

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;
}``````

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

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

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

Graph is fine but it could also be solved much easier using DP for the Longest Increasing Subsequence: en.wikipedia.org/wiki/Longest_increasing_subsequence

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

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.

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

Can any one give me the idea to implemrnt this in java

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

Is there no starting and ending point? Looks like an all-pair longest path.

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

there is no start and end point...

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

dynamic programming

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

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.

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

you can't modify floyd warshall as explained by you as it has no optimal substructure.

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

the input can be converted into a tree with each node having left right down and up children nodes and then do depth first algorithm

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

what is the time complexity ? can you please write algorithm or code in java?

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.