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

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE coding round, one problem the whole time: design a data structure supporting insert and k-th largest retrieval with duplicates. Felt like a clean problem on the surface but the efficiency requirement is where they really wanted to dig in.

Questions Asked (1)

Design a data structure that supports insert(num) and findLargest(k), where findLargest returns the k-th largest element (0-indexed, duplicates allowed). Optimize findLargest as much as possible.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was just a sorted list with bisect.insort, which gets you O(log n) insert but O(1) findLargest since you can index directly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify requirements and constraints first, then propose a balanced BST augmented with subtree sizes to support O(log n) insert and O(log n) findLargest. Discuss trade-offs with other approaches like heaps or Fenwick trees, and optimize findLargest by maintaining order statistics.

Pro tip: Mention that Google often values clean, scalable solutions; emphasize that the augmented BST approach is optimal for both operations and discuss how to handle duplicates by storing counts.

1. Clarify Requirements

Ask about constraints: expected number of operations, value range, memory limits, and whether findLargest is called frequently. Confirm that duplicates are allowed and 0-indexed k-th largest means k=0 returns the maximum.

2. Brainstorm Data Structures

Consider options: sorted array (O(n) insert), heap (O(log n) insert but O(k log n) findLargest), balanced BST with subtree sizes (O(log n) both), Fenwick tree over compressed values (O(log n) both). Evaluate trade-offs.

3. Select and Justify Optimal Approach

Choose an augmented balanced BST (e.g., Red-Black or AVL) where each node stores the size of its subtree. This allows finding the k-th largest in O(log n) by traversing from the root.

4. Detail Operations

Explain insert: standard BST insert, update subtree sizes on the path. Explain findLargest(k): traverse right subtree first, using sizes to skip subtrees, similar to finding k-th smallest but reversed.

5. Analyze Complexity and Edge Cases

State time complexity: O(log n) for both operations. Space: O(n). Handle duplicates by storing a count per node. Discuss edge cases: k out of bounds, empty tree, and large k.

Key Points to Mention

Augmented balanced BST with subtree sizes for order statistics
Time complexity: O(log n) for insert and findLargest
Handling duplicates by storing counts in nodes
Alternative approaches: Fenwick tree with coordinate compression, heaps, sorted arrays
Trade-offs: memory vs speed, simplicity vs optimality
Edge cases: k >= number of elements, empty tree, negative numbers

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