Adobe Interview Question


Country: United States




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

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):

// the following lines are in the header file "snake_length.h"

int HasRightPath(int r, int c)
{
	if (!((c + 1) < max_n_col))
		return 0;
	return ((matrix[r][c + 1] - matrix[r][c]) * 
		(matrix[r][c + 1] - matrix[r][c])) < 2;	
}

.
Let's define a BinaryTree structure to represent a vertex (for convenience, not optimal space wise)

int matrix[3][5] = {{1, 3, 2, 6, 8}, {-9, 7, 1, -1, 2}, {1, 5, 0, 1, 9}}; 

int max_n_row	= 3;
int max_n_col   = 5;

int max_rank = 0;

typedef struct BinaryTree {
	BinaryTree* right;	// Point to the vertex on the right
	BinaryTree* bottom;	
	int row;			// row index of this vertex (not necessary, just for readable code)
	int column;			// similar to above for column
	int rank;			/* Rank: distance from this vertex to the end of the longest
						   path originating (or similarly, involving) this vertex.
						*/
	int matrix_value;	// Value of the matrix at this vertex (not neceassry again since we already have the matrix)
} BinaryTree;

BinaryTree	bt_matrix[3][5];	// Graph vertices

First, we need to initialize the graph, e.g., every vertex should be connected to its right and bottom neighbors (if any)

int InitTree()
{
	// Connecting the vertices
	int r, c;
	for (r = 0; r < max_n_row; r++)
	{
		for (c = 0; c < max_n_col; c++)
		{
			BinaryTree dummy = {0, 0, r, c, 0, matrix[r][c]};
			memcpy(&bt_matrix[r][c], &dummy, sizeof(BinaryTree));	// Initialize this vertex
			if (HasRightPath(r, c))			
				bt_matrix[r][c].right		= &bt_matrix[r][c + 1];		// Connect to right vertex					
			if (HasBottomPath(r, c))			
				bt_matrix[r][c].bottom		= &bt_matrix[r + 1][c];		// Connect to bottom vertex					
		}
	}
	return 0;
}

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.

int Rank(struct BinaryTree* bt)
{
	if (bt == 0)
		return 0;
	if (bt->rank == 0)			
	{
		int rank_right = Rank(bt->right);
		int rank_bottom = Rank(bt->bottom);
		bt->rank = (rank_right > rank_bottom) ? rank_right : rank_bottom;		
		bt->rank += 1;	// To count the vertex itself
	};
	return bt->rank;
}

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

int FindRanks()
{
	int r, c;
	for (r = 0;r < max_n_row; r++)
		for (c = 0;c < max_n_col; c++)
		{
			int rank = Rank(&bt_matrix[r][c]);
			if (max_rank < rank)
				max_rank = rank;
		};

	return max_rank;
}

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.

int Print(int rank)
{
	int count = 0;
	int r, c;
	for (r = 0; r < max_n_row; r++)
	{
		for (c = 0;c < max_n_col; c++)
		{
			if (bt_matrix[r][c].rank == rank)			
			{
				int	path[100];				
				PrintSubTree(&bt_matrix[r][c], path, 0);
				count++;
			};			
		}
	}
	return count;
};

void PrintSubTree(BinaryTree* bt, int* path, int pos)
{
	path[pos] = bt->matrix_value;
	if ((bt->right == 0) && (bt->bottom == 0))
	{
		// End of a route (snake)
		int i = 0;		
		printf("Path of length %d: ", pos + 1);
		for (i = 0; i <= pos; i++)
			printf("%d ", path[i]);
		printf("\n");
		return;
	};
	
	if ((bt->right != 0) && (bt->bottom != 0))
	{
		// Route branching in two directions.
		if (bt->right->rank >= bt->bottom->rank)
			PrintSubTree(bt->right, path, pos + 1);
		if (bt->bottom->rank == bt->right->rank)
			PrintSubTree(bt->bottom, path, pos + 1);
	}
	else if (bt->right != 0)
		PrintSubTree(bt->right, path, pos + 1);
	else
		PrintSubTree(bt->bottom, path, pos + 1);
}

Sample code:

#include <stdio.h>
#include "snake_length.h"

int main()
{
	InitTree();
	printf("Max length for a snake = %d\n", FindRanks());
	Print(max_rank);
	getc(stdin);
	return 0;
}

Output:

Max length for a snake  = 5
Path of length 5: 3 2 1 0 1

A few notes:

1- 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

- Ehsan October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ehsan after building the graph cant we do a DFS and find out the path having maximum depth ?????

- codex May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ehsan June 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

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();
	}
    }
}

- thelineofcode October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This appears to be a straight forward and good solution.
What is the complexity of this solution ?

Thanks.

- CodeNinja March 06, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More