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

IntermediatePrefer not to say

Jul 2026

Summary

Google SWE coding round, one problem the whole session. Classic algorithmic puzzle that looks manageable until you realize the naive approach won't cut it at scale.

Questions Asked (1)

You're given a list of envelopes defined by width and height. An envelope can contain another only if both dimensions are strictly larger. What's the maximum number of envelopes you can nest inside each other?

Algorithms & Data Structures

Author's notes

I knew LIS was involved pretty quickly but fumbled the sorting step for a few minutes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a 2D version of the Longest Increasing Subsequence (LIS) problem. Sort envelopes by width ascending and, for equal widths, sort height descending to prevent nesting envelopes of the same width. Then find the LIS of the heights using an O(n log n) patience sorting approach.

Pro tip: Mention that sorting height descending for equal widths is crucial to avoid incorrectly counting multiple envelopes with the same width as nestable. Also, discuss edge cases like duplicate envelopes and the time/space complexity trade-offs.

1. Understand the problem

Clarify that an envelope can only contain another if both width and height are strictly larger. The goal is to find the maximum chain length.

2. Sort the envelopes

Sort by width ascending. For equal widths, sort by height descending. This ensures that when we process heights, we don't accidentally nest envelopes of the same width.

3. Reduce to LIS

Extract the heights in the sorted order. The problem now becomes finding the Longest Increasing Subsequence (LIS) of these heights.

4. Compute LIS efficiently

Use the patience sorting algorithm (binary search) to find the LIS in O(n log n) time. Alternatively, dynamic programming gives O(n^2) but is less optimal.

5. Return the result

The length of the LIS is the maximum number of envelopes that can be nested.

Key Points to Mention

Sorting by width ascending and height descending for ties.
Reduction to the Longest Increasing Subsequence (LIS) problem.
O(n log n) solution using patience sorting with binary search.
Handling of duplicate envelopes and strict inequality condition.
Time and space complexity analysis.
Edge cases: empty list, single envelope, all envelopes identical.

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