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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Pinterest.

What role is this question designed for?

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

Maximize Boxes Stored Through One Entrance

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two integer arrays: - `boxes[i]`: the height of the `i`-th box. - `rooms[j]`: the height limit of the `j`-th room in a linear warehouse. The warehouse has a single entrance on the left. To place a box into room `j`, the box must pass through every room from `0` to `j`, so its height must be no greater than the minimum height among `rooms[0..j]`. Each room can contain at most one box, and each box can be used at most once. You may reorder the boxes in any way before inserting them. Return the maximum number of boxes that can be placed into the warehouse. Follow-up: Instead of maximizing the number of boxes, return the maximum possible total height of the boxes placed into the warehouse.

Quick Answer: This question evaluates array manipulation, constraint reasoning, and optimization skills, touching on greedy and combinatorial allocation concepts under prefix capacity constraints.

Part 1: Maximum Number of Boxes Stored Through One Entrance

You are given two integer arrays, boxes and rooms. boxes[i] is the height of the i-th box, and rooms[j] is the height of the j-th room in a linear warehouse. The warehouse has a single entrance on the left. A box can be placed into room j only if it can pass through every room from 0 to j, so its height must be no greater than the minimum value in rooms[0..j]. Each room can hold at most one box, each box can be used at most once, and you may reorder the boxes before inserting them. Return the maximum number of boxes that can be placed into the warehouse.

Constraints

0 <= len(boxes), len(rooms) <= 2 * 10^5
1 <= boxes[i], rooms[j] <= 10^9 when the arrays are non-empty

Examples

Input: ([4, 3, 4, 1], [5, 3, 3, 4, 1])

Expected Output: 3

Explanation: The effective room heights become [5, 3, 3, 3, 1]. By reordering boxes, you can place boxes of heights 1, 3, and 4, so the answer is 3.

Input: ([1, 2, 2, 3, 4], [3, 4, 1, 2])

Expected Output: 3

Explanation: The effective room heights are [3, 3, 1, 1]. You can place boxes with heights 1, 2, and 2.

Input: ([], [1, 2, 3])

Expected Output: 0

Explanation: There are no boxes to place.

Input: ([5, 5, 5], [4, 4, 4, 4])

Expected Output: 0

Explanation: Every box is taller than every reachable room height, so none can be placed.

Input: ([2, 2, 3], [3, 3, 2, 2])

Expected Output: 3

Explanation: The effective room heights stay [3, 3, 2, 2]. All three boxes can be placed by using the two height-2 rooms first and then a height-3 room.

Input: ([1, 2], [])

Expected Output: 0

Explanation: There are no rooms in the warehouse.

Hints

First convert each room into its effective height: for room j, the true limit is min(rooms[0], rooms[1], ..., rooms[j]).
After preprocessing, the deepest rooms are the most restrictive. Sort the boxes and try to place the smallest remaining box into rooms from right to left.

Part 2: Maximum Total Height of Boxes Stored Through One Entrance

You are given two integer arrays, boxes and rooms. boxes[i] is the height of the i-th box, and rooms[j] is the height of the j-th room in a linear warehouse. The warehouse has a single entrance on the left. A box can be placed into room j only if it can pass through every room from 0 to j, so its height must be no greater than the minimum value in rooms[0..j]. Each room can hold at most one box, each box can be used at most once, and you may reorder the boxes before inserting them. Return the maximum possible total height of the boxes placed into the warehouse.

Constraints

0 <= len(boxes), len(rooms) <= 2 * 10^5
1 <= boxes[i], rooms[j] <= 10^9 when the arrays are non-empty
The answer fits in a signed 64-bit integer

Examples

Input: ([4, 3, 4, 1], [5, 3, 3, 4, 1])

Expected Output: 8

Explanation: The effective room capacities are [5, 3, 3, 3, 1]. The best choice is boxes 4, 3, and 1 for a total of 8.

Input: ([1, 2, 4, 5], [6, 5, 4])

Expected Output: 11

Explanation: The effective capacities are already [6, 5, 4]. Place boxes 5, 4, and 2 for a total of 11.

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

Expected Output: 0

Explanation: There are no boxes to place.

Input: ([1, 2, 3, 4], [4, 1, 3, 2])

Expected Output: 5

Explanation: The effective capacities become [4, 1, 1, 1]. Only boxes 4 and 1 can be used, so the maximum total is 5.

Input: ([2, 2, 2], [2, 2])

Expected Output: 4

Explanation: There are only two rooms, and both can store a box of height 2.

Input: ([7], [6])

Expected Output: 0

Explanation: The single box is too tall for the only room.

Hints

As in Part 1, replace each room by the minimum height seen so far from the left. That gives the true capacity of each room.
Process rooms from the most restrictive capacity to the least restrictive capacity. Keep all boxes that can fit so far, and greedily take the largest available one each time.

Quick Overview

This question evaluates array manipulation, constraint reasoning, and optimization skills, touching on greedy and combinatorial allocation concepts under prefix capacity constraints.