Find kth smallest in sorted matrix
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given an n x n matrix where each row and each column is sorted in nondecreasing order, and an integer k (1 ≤ k ≤ n^
2), return the k-th smallest element in the matrix. Compare approaches using a min-heap over row heads versus value-space binary search with counting, and analyze complexities and edge cases.
Quick Answer: This question evaluates algorithmic problem-solving and data-structure knowledge, focusing on selection in a row-and-column-sorted matrix and the comparative use of min-heaps versus value-space binary search along with time/space complexity and edge-case analysis.