Interview Question

Software Engineer Interview

-

Google

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
AnswerAdd Tags

Interview Answers

2 Answers

1

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

Anonymous on

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>; int longestEndingAt(int i, int j, mat_t &longestEndingAtMatrix, const mat_t &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[0].size())) continue; if(M[i + dx][j + dy] == M[i][j] - 1) { auto current = longestEndingAt(i + dx, j + dy, longestEndingAtMatrix, M) + 1; if(current > longest) longest = current; } } } longestEndingAtMatrix[i][j] = longest; return longest; } int longest(mat_t M) { mat_t longestEndingAtMatrix(M.size(),vector(M[0].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 << longest(A) << endl; return 0; } output: 4 complexity: O(n^2)

Mhret on

Add Answers or Comments

To comment on this, Sign In or Sign Up.