โ† Microsoft questions
CodingReported in a candidate post, Apr 2021

Array Processing with Priority Queue

Filed under Microsoft

Free read 3 of 3

Determine if elements can have duplicates and whether memory constraints restrict storing the entire array in a heap.

The question

Solve an array manipulation problem efficiently using a priority queue or heap approach.

Constraints

  • Array size up to 10^5 elements
  • Time limit strictness requires O(n log k) or better

Examples

Input
nums = [3,2,1,5,6,4], k = 2
Output
5
Why
Finds the 2nd largest element using a min-heap of size k.

Approach

  1. Determine if elements can have duplicates and whether memory constraints restrict storing the entire array in a heap.

Solution

O(n log k) time, O(k) space

Python
import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]

Tips

  • What they are testing: Test with duplicate elements, k equals 1, and k equals the array length.
  • Common mistake: Using a max-heap for finding the k-th largest element when a min-heap of size k is more space-efficient.

Related Microsoft questions

Collected from public candidate posts and coding forums. Updated Nov 2026.