Car Pooling
You are working as a cab driver. Your car moves in a straight line and moves toward the forward direction only. Initially, you have ‘C’ empty seats for the passengers.

Now, you are given ‘N’ number of trips that you have to make. In each trip, you are given three integers ‘Num’, ‘pickPoint’, and ‘dropPoint’ denoting that there are ‘Num’ numbers of passengers standing at 'pickpoint’ and you have to drop them at 'droppoint’.

Your task is to find if it is possible to pick up and drop off all the passengers of all the given trips or not.

Note :

You have a special type of car containing any number of seats.

Input Format :

The first line contains a single integer ‘T’, denoting the number of test cases. Each test case’s first line contains ‘C’ and ‘N’, denoting the car’s capacity and the number of trips you have to make. The next ‘N’ lines contain 3 integers, each denoting the number of passengers, pick up point, and drop point of the trip respectively.

Output Format :

For each test case, print “True” if possible to make the trip and “False” otherwise. Print the output of each test case in a separated line.

Note :

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Car Pooling

You are working as a cab driver. Your car moves in a straight line and moves toward the forward direction only. Initially, you have ‘C’ empty seats for the passengers.

Now, you are given ‘N’ number of trips that you have to make. In each trip, you are given three integers ‘Num’, ‘pickPoint’, and ‘dropPoint’ denoting that there are ‘Num’ numbers of passengers standing at 'pickpoint’ and you have to drop them at 'droppoint’.

Your task is to find if it is possible to pick up and drop off all the passengers of all the given trips or not.

Note :

You have a special type of car containing any number of seats.

Input Format :

The first line contains a single integer ‘T’, denoting the number of test cases.

Each test case’s first line contains ‘C’ and ‘N’, denoting the car’s capacity and the number of trips you have to make.

The next ‘N’ lines contain 3 integers, each denoting the number of passengers, pick up point, and drop point of the trip respectively.

Output Format :

For each test case, print “True” if possible to make the trip and “False” otherwise.

Print the output of each test case in a separated line.

Note :

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= C <= 10^5
1 <= N <= 10^3
0 <= passengers <= 100
0 <= pickPoint, dropPoint <= 1000

Where ‘T’ is the number of test cases, ‘C’ is the car’s capacity, and “N’ is the number of trips you have to make.

Time limit: 1 sec.

Accepted Answer

Hash Map Implementation

The simple idea is that we will keep a record of the number of passengers changed at every time in a hash map ‘passengers’ where the key represents the time at which the number of passengers changed and the value at that key represents the count of passengers changed.

For Example- If we have trips = [ 2, 1,4 ], [ 2, 2,5 ] then at time = 1, no of passengers changed and increased by 2. So passengers[ 1 ] = 2. At time = 4, these passengers reach their destination so at time = 4, no of passengers get reduced by 2. So passengers[ 4 ] = -2.

Similarly passengers[ 2 ] = 2 and passengers[ 5 ] = -2.

In the hash map, we will increment the value at the pickup point of the ‘i-th’ trip and decrement the value at the drop point of the ‘i-th’ trip by the number of passengers in the ‘i-th’ trip.

As in the hash map, keys are stored in sorted order. So adding the values of this hash map will give the number of passengers at every key time. If no of the passengers exceeds the capacity of the car at any time, we will return false.

Algorithm

Initialize a hash map ‘passengers’ that maps from integer to integer.
Run a loop i: 0 to N - 1 to check every trip detail.
- Increment passengers[ trip[ i ][ 1 ] ] by trip[ i ][ 0 ].
- Decrement Passengers[ trip[ i ][ 2 ] ] by trip[ i ][ 0 ].
Traverse through the hash map.
- Store the sum of values of the hash map in a variable ‘count’.
- If count > C( capacity ), return false.
Return true.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of trips.

We are using a hash map to store every trip’s details, making space complexity O(N).

Time Complexity: O(nlogn)Explanation:

O( N*log(N) ), where ‘N’ is the number of trips.

We are storing every trip value in a hash map that will take O(N*log(N)) time and then iterating through the hash map that will cost O(N) time. So the overall time complexity is O(N) + O(N*log(N)) = O(N*log(N)).

Java (SE 1.8)

/* 

    Time Complexity : O(N*log(N))

    Space Complexity : O(N)

    

    where 'N' is the number of trips.

*/



import java.util.TreeMap;

import java.util.Map.Entry;



public class Solution {

    public static boolean carPooling(int[][] trips, int n, int c) {



        // Initializing map to store number of passengers changed at any time.

        TreeMap passengers = new TreeMap<>();



        // Iterate through all the trips.

        for (int i = 0; i < n; i++) {



            if (passengers.get(trips[i][1]) == null) {

                passengers.put(trips[i][1], 0);

            }



            if (passengers.get(trips[i][2]) == null) {

                passengers.put(trips[i][2], 0);

            }



            // Increment passengers at pick point of 'i-th' trip.

            passengers.put(trips[i][1], passengers.get(trips[i][1]) + trips[i][0]);



            // Decrement passengers at drop point of 'i-th' trip.

            passengers.put(trips[i][2], passengers.get(trips[i][2]) - trips[i][0]);



        }



        // Initialize variable to store count of passengers.

        int count = 0;



        // Iterate through the map.

        for (Entry e : passengers.entrySet()) {



            count = count + e.getValue();



            // Return false, if count of passengers> capacity of car.

            if (count > c) {

                return false;

            }



        }



        return true;



    }

}

Python (3.5)

"""
    Time Complexity : O(N*log(N))
    Space Complexity : O(N)
    
    where 'N' is the number of trips.
"""



def carPooling( trips,  n,  c):

    
    # Initializing map to store number of passengers changed at any time.
    passengers={}

    # Iterate through all the trips.
    for i in range(n):
    
        if(trips[i][1] not in passengers):
            passengers[trips[i][1]]=0
        
        if(trips[i][2] not in passengers):
            passengers[trips[i][2]]=0

        # Increment passengers at pick point of 'i-th' trip.
        passengers[trips[i][1]] = passengers[trips[i][1]] + trips[i][0]

        # Decrement passengers at drop point of 'i-th' trip.
        passengers[trips[i][2]] = passengers[trips[i][2]] - trips[i][0]
    

    # Initialize variable to store count of passengers.
    count = 0

    

    # Iterate through the map.
    for itr in sorted(passengers.keys()):
    
        count = count + passengers[itr]
        
        # Return False, if count of passengers> capacity of car.
        if (count > c):
        
            return False
        
    

    return True

C++ (g++ 5.4)

/* 

    Time Complexity : O(N*log(N))

    Space Complexity : O(N)

    

    where 'N' is the number of trips.

*/



#include 



bool carPooling(vector> trips, int n, int c)

{



    // Initializing map to store number of passengers changed at any time.

    map passengers;



    // Iterate through all the trips.

    for (int i = 0; i < n; i++)

    {



        // Increment passengers at pick point of 'i-th' trip.

        passengers[trips[i][1]] = passengers[trips[i][1]] + trips[i][0];



        // Decrement passengers at drop point of 'i-th' trip.

        passengers[trips[i][2]] = passengers[trips[i][2]] - trips[i][0];

    }



    // Initialize variable to store count of passengers.

    int count = 0;



    map::iterator itr;



    // Iterate through the map.

    for (itr = passengers.begin(); itr != passengers.end(); itr++)

    {

        count = count + itr->second;



        // Return false, if count of passengers> capacity of car.

        if (count > c)

        {

            return false;

        }

    }



    return true;

}

Accepted Answer

Efficient Approach

The range for staring and ending location varies from 0 to 1000 which is not a large range.

We will solve the problem as we did in the previous approach, but instead of using a hash map, we will take a 1-D array ‘passengers’ where passengers[ i ] denotes the number of passengers changed at ‘i-th’ time.

By doing this, we can update every trip detail in a constant time which was taking (log(N)) time in case of hash map.

Algorithm

Initialize a 1-D array ‘passengers’ of size ‘1001’ with all values ‘0’.
Run a loop i: 0 to N - 1 to check every trip detail.
- Increment passengers[ trip[ i ][ 1 ] ] by trip[ i ][ 0 ].
- Decrement Passengers[ trip[ i ][ 2 ] ] by trip[ i ][ 0 ].
Initialize a variable ‘count’ with the value ‘0’.
Traverse through the ‘passengers’ array, i: 0 to 1000
- Increment ‘count’ by passengers[ i ].
- If count > C, return false.
Return true.

Space Complexity: O(1)Explanation:

O(1)

We have taken an array ‘passengers’ of size ‘1001’ that is of constant size. So the space complexity is O(1).

Time Complexity: OtherExplanation:

O( max( N,k) ), where ‘N’ is the number of trips and ‘k’ is the range between starting and ending location.

At first, we iterate through all the trips that take O(N) time and then iterate through the ‘passengers’ array that takes O(k), So the time complexity is O( max(N,k) ).

Java (SE 1.8)

/* 

    Time Complexity : O(max(k,N))

    Space Complexity : O(1)

    

    where 'N' is the number of trips and 

    'k' is range between starting and ending location

*/



public class Solution {



    public static boolean carPooling(int[][] trips, int n, int c) {



        // Initializing a variable to store maximum location point.

        int k = 1001;



        // Initializing array to store number of passengers changed at any time.

        int[] passengers = new int[k];



        // Iterate through all the trips.

        for (int i = 0; i < n; i++) {

            passengers[trips[i][1]] = passengers[trips[i][1]] + trips[i][0];



            passengers[trips[i][2]] = passengers[trips[i][2]] - trips[i][0];

        }



        int count = 0;



        // Check count of passengers at any time.

        for (int i = 0; i < k; i++) {

            count = count + passengers[i];



            // If count of passengers is more than capacity of car.

            if (count > c)

                return false;

        }



        return true;



    }



}

C++ (g++ 5.4)

/* 

    Time Complexity : O(max(k,N))

    Space Complexity : O(1)

    

    where 'N' is the number of trips and 

    'k' is range between starting and ending location

*/



#include 



bool carPooling(vector > trips, int n, int c)

{

	// Initializing a variable to store maximum location point.

    int k = 1001;

    

    // Initializing array to store number of passengers changed at any time.

    vector passengers(k, 0);

    

    // Iterate through all the trips.

    for (int i = 0; i < n; i++)

    {

        passengers[trips[i][1]] = passengers[trips[i][1]] + trips[i][0];



        passengers[trips[i][2]] = passengers[trips[i][2]] - trips[i][0];

    }



    int count = 0;

    

    // Check count of passengers at any time.

    for (int i = 0; i < k; i++)

    {

        count = count + passengers[i];

        

        // If count of passengers is more than capacity of car.

        if (count > c)

            return false;

    }



    return true;

}

Python (3.5)

"""
    Time Complexity : O(max(k,N))
    Space Complexity : O(1)
    
    where 'N' is the number of trips and 
    'k' is range between starting and ending location
"""



def carPooling(trips, n, c):

	# Initializing a variable to store maximum location point.
    k = 1001
    
    # Initializing array to store number of passengers changed at any time.
    passengers=[0]*k
    
    # Iterate through all the trips.
    for i in range(n):
    
        passengers[trips[i][1]] = passengers[trips[i][1]] + trips[i][0]

        passengers[trips[i][2]] = passengers[trips[i][2]] - trips[i][0]
    

    count = 0
    
    # Check count of passengers at any time.
    for i in range(k):
    
        count = count + passengers[i]
        
        # If count of passengers is more than capacity of car.
        if (count > c):
            return False
    

    return True

You are working as a cab driver. Your car moves in a straight line and moves toward the forward direction only. Initially, you have ‘C’ empty seats for the passengers.

Now, you are given ‘N’ number of trips that you have to make. In each trip, you are given three integers ‘Num’, ‘pickPoint’, and ‘dropPoint’ denoting that there are ‘Num’ numbers of passengers standing at 'pickpoint’ and you have to drop them at 'droppoint’.

Your task is to find if it is possible to pick up and drop off all the passengers of all the given trips or not.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Fractal Analytics Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Fractal Analytics Software Engineer