FastPrepFastPrep
Problem Brief

Minimum Cars to Remove

OA
See Microsoft online assessment and 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.

1Example 1

Input
weights = [3, 5, 2, 6, 1], capacity = 8
Output
0
Explanation
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.

2Example 2

Input
weights = [3, 7, 2, 6, 1], capacity = 8
Output
1
Explanation
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

Limits and guarantees your solution can rely on.

  • The size of the array is up to 10^5.
  • The weight of each car is up to 10^9.
public int minimumCarsToRemove(int[] weights, int capacity) {
  // write your code here
}
Input

weights

[3, 5, 2, 6, 1]

capacity

8

Output

0

Sign in to submit your solution.