Google Interview Question: A square matrix of size n^2 a... | Glassdoor.com.au

## Interview Question

Software Engineer Interview

# A square matrix of size n^2 and random entries from

0 ... n^2, find the longest sequence of consecutive neighbours (i.e. top, left, bottom, right entries).
Tags:
algorithm

1

I first devised an O(n^4) algorithm but with the help of the interviewer we formulated one in O(n^2).

Interview Candidate on 20 Nov 2014
0

Using dynamic programming.

LengthOfLongestSequenceEndingAt(i, j) is 1 if none of the eight neighbors of matrix[i][j] are one less than matrix[i][j]. If it has a consecutive neighbor, LengthOfLongestSequenceEndingAt(i, j) is 1 + LengthOfLongestSequenceEndingAt of the neighbor with the highest LengthOfLongestSequenceEndingAt.

The answer then is the maximum LengthOfLongestSequenceEndingAt(i,j) for all i's and j's.

Below is a C++ implementation:

#include
#include
using namespace std;
using mat_t = vector&gt;;
int longestEndingAt(int i, int j, mat_t &amp;longestEndingAtMatrix, const mat_t &amp;M) {
if(longestEndingAtMatrix[i][j] != 0) return longestEndingAtMatrix[i][j];

int longest = 1;
for(auto dx : {-1, 0, 1}) {
if((i + dx = M.size())) continue;
for(auto dy : {-1, 0, 1}) {
if((j + dy = M.size())) continue;
if(M[i + dx][j + dy] == M[i][j] - 1) {
auto current = longestEndingAt(i + dx, j + dy, longestEndingAtMatrix, M) + 1;
if(current &gt; longest) longest = current;
}
}
}
longestEndingAtMatrix[i][j] = longest;
return longest;

}

int longest(mat_t M) {
mat_t longestEndingAtMatrix(M.size(),vector(M.size(), 0));
int result = 0;
for(int i = 0; i result) result = d;
}
}
return result;
}
int main() {
mat_t A = {{2, 3, 4},{8, 7, 7},{5, 6, 5}};
cout &lt;&lt; longest(A) &lt;&lt; endl;
return 0;
}
output: 4
complexity: O(n^2)

Mhret on 29 Nov 2014