Adobe Interview Question
Country: United States
Ehsan after building the graph cant we do a DFS and find out the path having maximum depth ?????
I suppose so. What I have done above is not all that different. It is a graph discovery. I did not use the right terminology though since the underlying graph is not a tree, but a DAG. However, the idea of rank where rank here is the distance to the furthest away node. Since we calculate the rank for each node only once, the total run time is the number of elements, which is the same as DFS.
I guess DFS is simple to explain though. All you need to remember is the depth of your stack.
Use DP approach:
1) Create auxiliary array say 'l' which has the same size as the original array.
2) In array 'l[i][j]' store max length of snake sequence which starts at point (i,j)
3) Perform flood fill algo on the original array to populate 'l' array like that:
- go [i][j+1] or/and [i+1][j] if the difference between point (i,j) and its neighbors is +-1
4) Find max element in array 'l' (there may be many points with the same value) and starting from that points print the sequences.
Code:
package adobe;
public class SnakeSeq {
public static void main(String[] args) {
int[][] arr = { { 1, 3, 2, 6, 8 }, { -9, 7, 1, -1, 2 }, { 1, 5, 0, 1, 9 } };
findSnakeSeq(arr);
}
public static void findSnakeSeq(int[][] m) {
int[][] l = new int[m.length][m[0].length];
int maxLength = 0;
for (int i = 0; i < l.length; i++) {
for (int j = 0; j < l[0].length; j++) {
if (l[i][j] == 0) {
int res = fillSeqLength(i, j, m, l);
if (res > maxLength) {
maxLength = res;
}
}
}
}
printMatrix(l);
printSequences(m, l, maxLength);
}
public static int fillSeqLength(int i, int j, int[][] m, int[][] l) {
if (i < 0 || j < 0 || i >= m.length || j >= m[0].length) {
return 0;
}
if (l[i][j] != 0) {
return l[i][j];
}
int right = 0;
int down = 0;
if (j + 1 < m[0].length && (m[i][j + 1] == m[i][j] + 1 || m[i][j + 1] == m[i][j] - 1)) {
right = fillSeqLength(i, j + 1, m, l);
}
if (i + 1 < m.length && (m[i + 1][j] == m[i][j] + 1 || m[i + 1][j] == m[i][j] - 1)) {
down = fillSeqLength(i + 1, j, m, l);
}
l[i][j] = Math.max(right, down) + 1;
return l[i][j];
}
public static void printSequences(int[][] m, int[][] l, int maxLength) {
for (int i = 0; i < l.length; i++) {
for (int j = 0; j < l[0].length; j++) {
if (l[i][j] == maxLength) {
printSequences(m, l, i, j, maxLength);
}
}
}
}
public static void printSequences(int[][] m, int[][] l, int i, int j, int maxLength) {
while (maxLength > 0) {
System.out.print(m[i][j] + " ");
maxLength -= 1;
if (j + 1 < m[0].length && l[i][j + 1] == maxLength
&& (m[i][j + 1] == m[i][j] + 1 || m[i][j + 1] == m[i][j] - 1)) {
j++;
continue;
}
if (i + 1 < m.length && l[i + 1][j] == maxLength
&& (m[i + 1][j] == m[i][j] + 1 || m[i + 1][j] == m[i][j] - 1)) {
i++;
continue;
}
}
}
private static void printMatrix(int[][] m) {
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
System.out.print(m[i][j] + " ");
}
System.out.println();
}
}
}
Input: Matrix "A" (given above)
Idea: You can look at your matrix as a graph where each element on the matrix "A" is a vertex.
There might be an edge between vertex A[i][j] and A[i + 1][j] (bottom) or A[i][j] and A[i][j + 1] (right).
For instance, the following function determines if there is an edge from (r, c) to (r, c + 1) (RIGHT):
.
Let's define a BinaryTree structure to represent a vertex (for convenience, not optimal space wise)
First, we need to initialize the graph, e.g., every vertex should be connected to its right and bottom neighbors (if any)
Next, we need to find the rank of each vertex:
IDEA: Rank(A[i][j]) = max(Rank(A[i][j].right, A[i][j].bottom)) + 1.
Find the rank for all the vertices in O(nm) time. Store the maximum which will be the length of longest snake (length of a snake = number of vertices involved ==> always positive).
At this stage, we are done unless you want to find paths of certain rank, e.g., max rank. Since we have already loaded a lot of info in our BinaryTree structure, we can easily do this recursively.
Sample code:
Output:
A few notes:
- Ehsan October 16, 20131- This is obviously not a good way to "print" a path since two different path might look the same
2- You can use function "Print(int)" for other path lengths