Interview Questions

Given a matrix of integers sorted along each row and each column, implement a rapid search algorithm

Microsoft Interview Questions and Answers


(Continued from previous question...)

271. Given a matrix of integers sorted along each row and each column, implement a rapid search algorithm

Question:
Given a matrix of integers sorted along each row and each column, implement a rapid search algorithm


maybe an answer:


You can do binary search. Look at top left, bottom right element and middle element of the matrix. If the search is between top left and mid then consider that submatrix. Similarly for other matrices. Ultimately you will have just one element to compare with.


maybe an answer2:


start with top right element loop:
compare this element(e) with m
i) if they are equal then return its position
ii) e<m then move it to down (if outof bound of matrix then break return false)
ii) e>m then move it to left (if outof bound of matrix then break return false)
repeat the "loop" till u find element or returned false
This will work for M*N matrix(not only for N*N)
Order would be O(M+N), for above case it will be O(2N)

(Continued on next question...)

Other Interview Questions