Question d'entretien d'embauche Google: Assume a matrix of integers t... |

Question d'entretien d'embauche

Entretien de Software Engineer In Test Hyderâbâd (Inde)

Assume a matrix of integers they are sorted in boh row and

  column vice .. how do u find a given number from the matrix in a optimal way?

Réponse de l'entretien

10 réponses


Let the matrix is n*m matrix. Then O(n log m) solution is trivial (binary search in each row). There is a easy O(n+m) solution too. The idea is to start from upper right corner (mat[0][m-1]) and traverse toward lower left corner (mat[n-1][0]). On the way check each entry and depending on whether larger go left or down. If there is a solution you will find it on the way. Or you will arrive to a point where you can no longer move without going out of the matrix. Either way you will check at most O(n+m) entries thus the solution in O(n+m).

Utilisateur anonyme, le 15 avr. 2010

I think it could be done even better than in O(n+m). Instead of starting at the upper right corner do a binary search on last column and find the biggest element that is still smaller than the given number. Say it's gonna be A[i, m-1]. Now we could throw away all rows up to an including i (since A[i, m-1] is larger than all of these elements) and the last column. Repeat everything for a smaller matrix of size (n - i, m - 1);

dp, le 21 mai 2010

To elaborate a little on dp's idea and add my take on it I would do a binary search on the last column to find the interval where the number is in. This interval will be one row within the matrix (assuming the value is not in the last column) and to find the interval should be O(log n). Then I would do a binary search on the row that remains which should cost O(log m). Combined that would be O(log n) + O(log m). Let me know what you guys think of this solution.

Utilisateur anonyme, le 8 sept. 2010

Anonymous, consider the matrix and you are searching for 9. Using this new algorithm we would look at rows 2 and 3 since 8 < 9 < 10 and completely miss 9 in the last row.
(1 3 5 7)
(2 3 6 8)
(3 5 8 10)
(6 9 11 12)

Me, le 2 déc. 2010

what do you do if the first element in the last column is already larger than the target? I.e. there may be no number that is smaller that the target. You could throw away that column, but that's it, I think. If so, the worst case becomes O(m).

Ethelbert, le 4 janv. 2011

What if you did a binary search on the diagonal....

Ethelbert, le 4 janv. 2011

A better solution than O[log(mn)] is unlikely. An mxn array can be laid in memory as a m*n one dimensional array at its base form. So a matrix sorted by row and column simply means this mxn one dimensional array is sorted. A binary search will get you the result in O[log(mn)], that is the fastest solution available.

Utilisateur anonyme, le 24 mars 2011

How about this.
for m columns - do binary range_search.
As in, start with m/2 th column, if the number is in this range...col(0) O (log(m+n))

matrix, le 1 juin 2012

oops, there is a catch....
If the number is in a range, it can be in that column, or any of the columns towards left of it....and in some cases, if its in the range.. it can still be on any columns on right.....
need to tweak a bit more.

matrix., le 1 juin 2012

Ok writing this 3rd time , no one will see this but for the sake of it,

Using radix sort
Take 10 buckets and enter all numbers respectively.
For example all numbers unit digit with 9 will in 9 number bucket.
Just divide the given number (input) and into parts , using mod operator.
And using the divided number"s unit digit find that index in the bucket.

Tada .
Radix sort way the. Linear search way to find the number

Complexity O ( n )


Utilisateur anonyme, le 10 juin 2017

Ajouter des réponses ou des commentaires

Pour commenter ceci, se connecter ou s'inscrire