Find kth smallest pair sum with heaps
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You are given two nondecreasing arrays A (length n) and B (length m) of non-negative integers and an integer k (1 <= k <= n*m). Return the k-th smallest value among all pair sums A[i] + B[j]. Avoid generating all pairs.
Target complexity: O(k log min(n, m)) time and O(min(n, m)) space using a heap-based approach. Discuss handling duplicate sums, boundary cases (k=1, k=n*m), and prove correctness.
Quick Answer: This question evaluates algorithmic problem-solving and complexity-analysis skills, focusing on efficient selection from two sorted arrays while handling duplicate sums and boundary conditions; it belongs to the Coding & Algorithms domain.