Meta OA Interview Coding Questions: Top K Frequent Elements and Kth Smallest Element in a Sorted Matrix

Top K Frequent Elements

Description:

Given a non-empty array of integers, return up to k most frequent elements.

For example:

• Given [1,2,1,1,2,3] and k = 2, return [1,2].
• Given [1,1,1,1] and k = 1, return [1].
• Given [3,2,1,2,3] and k = 2, return [2,3].
• Given [1,2,3,4] and k = 2, return [1,2].

Assume valid k and valid integers.

Kth Smallest Element in Sorted Matrix

Description:

Given an n x n matrix where each of the rows and columns are sorted in non-decreasing order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [[1, 5, 9],
  [10, 11, 13],
  [12, 13, 15]
]

If k = 1, return 1.
If k = 2, return 5.
If k = 8, return 13.

Note: You may assume k is always valid, 1 <= k <= n^2.

Restriction:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n^2

This set covers two classic interview problems: Top K Frequent Elements and Kth Smallest Element in a Sorted Matrix. The first is typically solved with a frequency map plus a heap, bucket sort, or quickselect to retrieve the k most frequent values efficiently. The second uses the matrix’s row- and column-sorted property, often with binary search on the value range and a counting pass to determine how many entries are less than or equal to mid. Together, they test frequency counting, top-k selection, and binary-search-on-answer techniques.