How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find Maximum Envelope Nesting | Google Coding Question

Find Maximum Envelope Nesting

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a list of envelopes, where each envelope is represented by `[width, height]`. One envelope can be placed inside another only if both its width and height are strictly smaller than the other envelope's. Envelopes cannot be rotated. Return the maximum number of envelopes that can be nested. Example: - Input: `[[5,4],[6,4],[6,7],[2,3]]` - Output: `3` - Explanation: One valid nesting chain is `[2,3] -> [5,4] -> [6,7]`. Assume the input size can be large enough that an efficient solution is required.

Quick Answer: This question evaluates algorithmic problem-solving skills, particularly reasoning about multi-dimensional ordering, sequence optimization, and time-complexity analysis.

You are given a list of envelopes, where each envelope is represented by [width, height]. One envelope can be placed inside another only if both its width and height are strictly smaller than the other envelope's. Envelopes cannot be rotated. Return the maximum number of envelopes that can be nested. For example, given [[5,4],[6,4],[6,7],[2,3]], the answer is 3 because one valid chain is [2,3] -> [5,4] -> [6,7]. The input can be large, so an efficient solution is required.

Constraints

0 <= len(envelopes) <= 100000
1 <= width, height <= 1000000000
Envelopes cannot be rotated
Envelope A can fit into envelope B only if A.width < B.width and A.height < B.height

Examples

Input: [[5, 4], [6, 4], [6, 7], [2, 3]]

Expected Output: 3

Explanation: A valid nesting is [2,3] -> [5,4] -> [6,7], so the maximum count is 3.

Input: []

Expected Output: 0

Explanation: With no envelopes, no nesting is possible.

Input: [[1, 1]]

Expected Output: 1

Explanation: A single envelope can form a nesting chain of length 1 by itself.

Input: [[4, 5], [4, 6], [6, 7], [2, 3], [1, 1]]

Expected Output: 4

Explanation: One optimal chain is [1,1] -> [2,3] -> [4,5] -> [6,7]. Envelopes [4,5] and [4,6] cannot nest because their widths are equal.

Input: [[2, 2], [2, 3], [2, 4]]

Expected Output: 1

Explanation: All envelopes have the same width, so none can fit into another. The maximum chain length is 1.

Input: [[5, 4], [6, 4], [6, 7], [2, 3], [7, 8], [7, 8]]

Expected Output: 4

Explanation: A longest valid chain is [2,3] -> [5,4] -> [6,7] -> [7,8]. The duplicate [7,8] does not increase the answer.

Hints

If you sort by width in ascending order, be careful with envelopes that have the same width.
After sorting correctly, the problem can be reduced to finding the length of a longest increasing subsequence on heights.

Quick Overview

This question evaluates algorithmic problem-solving skills, particularly reasoning about multi-dimensional ordering, sequence optimization, and time-complexity analysis.