How should I practice Minimum Cars to Remove?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Minimum Cars to Remove associated with Microsoft?

FastPrep tags this as a Microsoft coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Array

Minimum Cars to Remove

● HardMicrosoftOA

See Microsoft hiring insights

There is a bridge and cars are queued up at the entry of the bridge. Each car has a weight and at once only two cars can go to the bridge. the cars enter and exit the bridge in the same order as given in the array. For example, initially the first two cars enter the bridge, then the first car leaves and the third car arrives, then second car leaves and fourth car arrives and so on. The bridge has a capacity and if the total weight of the cars on the bridge exceeds that capacity, it will break. We can remove as many cars from the queue as we want and the relative order of the rest of the cars will remain the same. Find the minimum number of cars to remove so that the bridge doesn't break.

Examples

01 · Example 1

weights = [3, 5, 2, 6, 1]
capacity = 8
return = 0

Initially: Cars 3 and 5 enter the bridge. Combined weight: 3 + 5 = 8 (which is okay, doesn't exceed capacity). Car 3 leaves, Car 2 enters. Now on bridge: 5 and 2. Combined weight: 5 + 2 = 7 (okay). Car 5 leaves, Car 6 enters. Now on bridge: 2 and 6. Combined weight: 2 + 6 = 8 (okay). Car 2 leaves, Car 1 enters. Now on bridge: 6 and 1. Combined weight: 6 + 1 = 7 (okay). In this scenario, we didn't have to remove any cars, and the bridge never broke. So, the minimum number of cars to remove is 0.

02 · Example 2

weights = [3, 7, 2, 6, 1]
capacity = 8
return = 1

Initial steps: Cars 3 and 7 enter. Weight: 3 + 7 = 10 > 8 → bridge breaks. So, we need to remove at least one car to prevent this. Which car should we remove? Option 1: Remove 7. Remaining sequence: [3, 2, 6, 1]. 3 and 2: 5 3 leaves, 6 enters: 2 and 6: 8 2 leaves, 1 enters: 6 and 1: 7 No breakage. Removed 1 car. Option 2: Remove 3. Remaining sequence: [7, 2, 6, 1]. 7 and 2: 9 > 8 → breaks. Doesn't work. Option 3: Remove other cars. For instance, remove 2. Sequence: [3, 7, 6, 1]. 3 and 7: 10 > 8 → breaks. Doesn't work. So, the best is to remove 7, resulting in removing 1 car. Hence, the minimum number is 1.

Constraints

The size of the array is up to 10^5.
The weight of each car is up to 10^9.