FastPrepMinimum Cars to Remove
Problems/Minimum Cars to Remove

Minimum Cars to Remove

Microsoft logoMicrosoft● HardOA

Updated Sep 2026

QuestionFunctionExamplesConstraints

Problem statement

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.

Function

minimumCarsToRemove(weights: int[], capacity: int) → int

Examples

Example 1

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

Example 2

weights = [3, 7, 2, 6, 1]capacity = 8return = 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.

More Microsoft interview questions

  • Config Store with Priority OverridesPHONE SCREEN · Seen Nov 2026
  • Bad Request AlertsONSITE INTERVIEW · Seen Nov 2026
  • Minimum Cost to Process Priority TasksOA · Seen Nov 2026
  • Most Visited Sprint MarkerOA · Seen Nov 2026
  • Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
  • Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
  • Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
  • Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
  • Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
  • Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Reschedule Meetings for Maximum Free TimeFivetran · OAFivetran interview questions
  • Earn the Most 🐝Capital One · OACapital One interview questions
  • Minimum Cost to Convert Products to Variant AAmazon · OA
  • Maximize Element FrequencyGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
  • Split Array to Minimize the Largest SumInfosys · OAInfosys interview questions
  • Sliding Window MedianAuxoAI · OA
  • Delete and Freeze GameRubrik · OARubrik interview questions
  • Lock CodeVisa · OAVisa interview questions
  • Starlink Beam PlannerSpaceX · OA · PHONE SCREENSpaceX interview questions
  • Most Segments That Sort the ArrayRippling · OARippling interview questions

Microsoft interview experiences

  • Microsoft OA Questions, October 2026: 4 Experiences
  • Microsoft Experienced SWE Phone Screen: 1 Experience
  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int minimumCarsToRemove(int[] weights, int capacity) {
      // write your code here
    }

}
Checking account…