Pinterest·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Pinterest ML Engineer interview with a tricky warehouse packing problem that adds a twist to a classic LC variant. The bidirectional push mechanic is what makes it interesting and also where I got tripped up.

Questions Asked (1)

You have two arrays representing box heights and warehouse room heights. Boxes can be pushed in from either the left or the right side, and each box must fit within the effective minimum height along its entire push path. What is the maximum number of boxes you can fit in the warehouse?

Algorithms & Data Structures

Author's notes

The bidirectional part is what got me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as choosing a split point where boxes are pushed from the left up to that point and from the right after it, with each box's height constrained by the minimum room height along its push path. Precompute prefix and suffix minimums of room heights, then for each possible split, count how many boxes can fit from each side using a greedy or binary search approach. The answer is the maximum total boxes over all splits.

Pro tip: Clarify with the interviewer whether boxes can be pushed in any order and whether the split point is fixed; this affects whether a greedy strategy works. Also, mention that the problem can be solved in O(n log n) or O(n) with two pointers, showing awareness of efficiency.

1. Understand the problem and constraints

Restate the problem to ensure clarity: boxes are pushed from left or right, each box must be ≤ the minimum room height along its path. Ask about input sizes, whether boxes can be reordered, and if the split point is predetermined.

2. Precompute path minimums

Compute prefix minimums of room heights for left pushes and suffix minimums for right pushes. This allows O(1) lookup of the effective height limit for any box pushed from a given side up to a certain index.

3. Determine maximum boxes per side for each split

For each possible split index, use the precomputed minimums to find how many boxes can be accommodated from the left (using boxes that fit) and from the right. This can be done greedily by sorting boxes or using two pointers if boxes are sorted.

4. Maximize over all splits

Iterate over all possible split points, compute the total boxes (left + right), and keep the maximum. Ensure that boxes are not double-counted and that the split respects the push directions.

5. Analyze complexity and edge cases

Discuss time and space complexity (e.g., O(n log n) with sorting, O(n) with two pointers if boxes sorted). Consider edge cases: no boxes fit, all boxes fit, empty arrays, and boxes taller than any room.

Key Points to Mention

Prefix and suffix minimum arrays to efficiently compute the effective height limit for any push path.
Greedy approach: to maximize boxes from one side, always pick the smallest boxes that fit under the current minimum height.
Two-pointer technique to count boxes from left and right simultaneously after sorting boxes.
Binary search on the number of boxes if the problem is monotonic (e.g., if we can fit k boxes, we can fit k-1).
Time complexity: O(n log n) due to sorting, or O(n) if boxes are already sorted; space complexity O(n) for prefix/suffix arrays.
Edge cases: boxes taller than all room heights, split at boundaries (all from left or all from right), and duplicate heights.

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