Microsoft

Round 1 – DSA | Difficulty: Medium I was asked a problem based on two integer arrays, "nums1" and "nums2", both sorted in non-decreasing order, and an integer "k". The task was to find the k pairs with the largest sums, where each pair consists of one element from each array. The goal was to return the k pairs having the largest possible sums. The problem is similar to LeetCode 373 – Find K Pairs with Smallest Sums, except that the actual interview question asked for the largest sums instead of the smallest. The constraints were: "1 <= nums1.length, nums2.length <= 10^5" "-10^9 <= nums1[i], nums2[i] <= 10^9" Both arrays are sorted in non-decreasing order. "1 <= k <= 10^4" "k <= nums1.length * nums2.length" The interviewer expected an optimal solution using a priority queue (heap). I proposed a priority-queue-based approach, but my solution was not optimal. I could not arrive at the expected optimal approach during the interview. Result: Rejected after Round 1. Preparation tip: Practise heap-based solutions for finding the k smallest/largest pair sums, focusing on how to avoid exploring every possible pair.