Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Google SWE coding round, one question the whole time. They wanted a full design and implementation with complexity analysis, not just a working solution.

Questions Asked (1)

Design and implement a KthLargest class that takes an integer k and an initial list of integers, supports a constructor and an add(val) method that inserts a value and returns the current k-th largest element. Target O(log k) time per insertion and O(k) space. Explain your data structure choice, handle duplicates, and walk through the complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Min-heap of size k, pretty standard once you see it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a min-heap of size k to maintain the k largest elements, where the root is the k-th largest. For each add, push the new value and if the heap exceeds size k, pop the smallest; then return the root. This gives O(log k) time per insertion and O(k) space.

Pro tip: Mention that a max-heap of all elements would be O(n) per insertion, and a sorted list would be O(n) due to shifting; the min-heap of size k is optimal. Also, clarify that duplicates are handled naturally because the heap stores values, not unique elements.

1. Clarify requirements and constraints

Confirm that k is valid (1 ≤ k ≤ initial size + number of adds) and that duplicates are allowed. Discuss expected input sizes to justify the need for O(log k) per insertion.

2. Choose the data structure

Select a min-heap of size k. Explain that it keeps the k largest elements seen so far, with the smallest among them at the root, which is the k-th largest.

3. Design the constructor and add method

In the constructor, initialize the heap with the first k elements (or all if fewer), then for each remaining element, if it's larger than the root, replace the root and heapify. For add, push the value, and if size > k, pop the root; then return the root.

4. Analyze complexity and handle edge cases

State that each add does at most one push and one pop, each O(log k), so O(log k) time. Space is O(k). Handle duplicates by allowing multiple equal values in the heap; they are treated as separate elements.

5. Test with examples

Walk through a small example, e.g., k=3, initial [4,5,8,2], add(3) returns 4, add(10) returns 5, etc., to demonstrate correctness and duplicate handling.

Key Points to Mention

Min-heap of size k maintains the k largest elements, root is k-th largest.
Time complexity: O(log k) per add due to heap operations.
Space complexity: O(k) for the heap.
Duplicates are handled naturally; heap can contain multiple equal values.
Alternative approaches (sorting, max-heap) have worse time complexity.
Edge cases: k=1, k larger than initial size, empty initial list.

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