Find the kth largest element in a sorted 2D array (the rows are sorted and the columns are sorted).

Question

Anonymous · Accepted Answer

Use a max heap where the values are (element, row, column).  Add the last row to the heap.  (The hint I was given was to add the first row).  Then start a loop where you extractMax, then add the element above the element you extracted to the heap.  When you have done k extractMaxes you are finished.

Interview Answer · Answer

Why do we need some data structure. We can derive the formula to find the ith row and jth column.

Anonymous · Answer

When you pull a value out of the heap you need to replace it with another element from the same column.  How do you know which column the heap value was from?

Anonymous · Answer

Traverse 2D matrix from top right.
If target==matrix[i][j], return matrix[i][j] (or true)
else if target

Bloomberg

Bloomberg Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches