Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jul 2026

Summary

Google SWE coding round with a heap-based problem. Pretty standard algorithmic stuff but the details matter more than you'd think.

Questions Asked (1)

Given two sorted arrays and an integer k, find all index pairs (i, j) such that the sums arr1[i] + arr2[j] are among the k smallest possible sums.

Algorithms & Data Structures

Author's notes

My first instinct was brute force all pairs and sort them, which works but blows up on large inputs.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints (e.g., whether arrays can contain duplicates, if k can exceed total pairs, and if the output should be sorted). Then propose a min-heap approach that starts with the smallest sum (0,0) and expands to neighbors (i+1,j) and (i,j+1), using a visited set to avoid duplicates. Discuss time complexity O(k log k) and space O(k), and compare with binary search on sum value if needed.

Pro tip: Mention that you would handle duplicates carefully by using a visited set or by skipping duplicate sums, and discuss how to avoid generating the same pair multiple times. Also, proactively ask about edge cases like k=0 or empty arrays to show thoroughness.

1. Clarify requirements and constraints

Ask about input sizes, whether arrays can have duplicates, if k is guaranteed ≤ n*m, and if the output should be sorted by sum. Confirm the definition of 'k smallest sums' and whether ties should be included.

2. Choose an efficient algorithm

Propose a min-heap (priority queue) approach: initialize with (0,0), then repeatedly pop the smallest sum and push (i+1,j) and (i,j+1) if within bounds and not visited. Alternatively, discuss binary search on the sum value to find the k-th smallest sum and then collect all pairs ≤ that sum.

3. Handle duplicates and visited states

Use a visited set (e.g., a 2D boolean array or hash set of encoded indices) to avoid pushing the same pair multiple times. If duplicates in sums are allowed, ensure the algorithm still returns exactly k pairs (or all pairs if ties extend beyond k).

4. Analyze complexity and trade-offs

State that the heap approach takes O(k log k) time and O(k) space. Mention that binary search takes O((n+m) log(maxSum)) time but may require additional steps to collect all pairs. Discuss which is better based on k relative to n*m.

5. Test with edge cases and walk through an example

Walk through a small example (e.g., arr1=[1,7,11], arr2=[2,4,6], k=3) to demonstrate correctness. Test edge cases: k=0, k > n*m, empty arrays, negative numbers, and large k.

Key Points to Mention

Min-heap (priority queue) to efficiently generate sums in increasing order.
Visited set to avoid duplicate pairs and ensure each pair is considered once.
Time complexity O(k log k) and space O(k) for the heap approach.
Alternative binary search on the sum value to find the k-th smallest sum, then collect all pairs ≤ that sum.
Handling duplicates in arrays and ensuring exactly k pairs (or all pairs if ties).
Edge cases: k=0, k > n*m, empty arrays, negative numbers, and large k.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.