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
Answer

Interview Answer

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

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>;
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 29 Nov 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.