Adobe Interview Question Software Engineer / Developers
Country: United States
Well n^2 is the worst case(brute force).
Simply scan
- initially for each row
- then for columns
- then for diagonals in forward and back ward direction
yes, while you do the scans each step will let to optimize for the next one. But its still n^2, being brute force.
Any better ideas ?
Whatever algorithm you want to design, i think its almost impossible to do it without traversing the whole matrix which itself is O(n^2). Your brute force will do it in 3 passes while mine will do in single pass only :)
Extra space used in my approach can be avoided by storing via bit compression within the given matrix.
just a question, when you change a cell to 0 (let's say during diagonal process), you would still want to check for longest queue of 1s in that row. but if you had changed that cell to 0 in diagonal run, that won't give you correct solution for row or column when their turn come to check, would it?
arr = [] n size array, each element is (int, int) ==> col_count, diag_count
initialize arr by the first row of matrix.
row_max = 0
col_max = 0
diag_max = 0
for i in range(1, M, 1):
for j in range (0, N,1):
scan for consecutive 1s, is it greater than row_max, yes change row_max
arr[j].col_count = (row[i][j]==1)?arr[j].col_count+1:0
arr[j].diag_count = (row[i][j]==1)?arr[j-1].diag_count+1:0
......
and the usual routine
if arr[j].col_count > col_max --> set col_max
......
Is the question also asking to consider the case wherein we might have to combined effective maximum of horizontal, vertical and diagonal trails?
Or is it just like have a result of each of these 3 and finding the maximum out of them?
mat[i][j] = mat[i][j]==max(mat[i-1][j] , mat[i][j-1], mat[i-1][j-1])+1 or 0 depending on the value of mat[i][j] .
mat[n][n] gives the answer. If we modify the original matrix itself then , we don't need to use any extra space. thus , it can be done with O(n^2) and O(1) space .
Simply traverse over to find the maximum in the matrix then .
1) Search in four directions from position (i,j) :
right, right-diagonal downwards, down, left-diagonal downwards.
2) Keep track of longest trail of 1's found so far. Also change 1 to 0 as you traverse a cell in matrix so that you dont need to check for that position again.
=> O(n^3)
OR
You can save at position (i,j) four values a,b,c,d:
Longest trail of 1's ending at (i,j) from four directions i.e left, right-diagnoal up, up and left-diagonal up.
Answer is max( temp[i][j].a, temp[i][j].b, temp[i][j].c, temp[i][j].d ) for all cells (i,j).
- Cerberuz October 08, 2012=> O(n^2)