Solution For Design Underground System

Problem description:

Design an underground system to track the traveling of the subway riders. Implement the following two methods:

1. void checkIn(int id, string stationName, int t)

2. A customer with id card ‘id’ checked in at station ‘stationName’ at time ‘t’.

3. A customer can only be checked into one place at a time.

4. void checkOut(int id, string stationName, int t)

5. A customer with id card ‘id’ checked out from station ‘stationName’ at time ‘t’.

Implement the following function:

1. double getAverageTime(string startStation, string endStation)

2. Returns the average time taken to travel between the startStation and the endStation.

Solution:

To solve this problem, we need to implement a class which handles the check-in and check-out of passengers, and also calculates the average time taken between two stations. We can use two hash tables to store the information of check-in and check-out.

• checkIn hash table: This hash table will store the information of passenger’s check-in time and station name, with the passenger’s ID as key.
• checkOut hash table: This hash table will store the information of passenger’s check-out time and station name, with the passenger’s ID as key.

We can also use a nested hash table to calculate the average time taken between two stations, where the outer hash table stores the information of start station and the inner hash table stores the information of end station with the average travel time as value.

Algorithm:

1. Create a class called UndergroundSystem. In the constructor, initialize the checkIn hash table, checkOut hash table, and travelTime hash table.

2. Define a checkIn() method which takes the ID, stationName, and time as input. Retrieve the current station name and time from the checkIn hash table using the ID and store the information in the hash table.

3. Define a checkOut() method which takes the ID, stationName, and time as input. Retrieve the check-in station name and time from the checkIn hash table using the ID, and store the check-out station name and time in the checkOut hash table. Calculate the travel time and store the information in the travelTime hash table.

4. Define a getAverageTime() method which takes startStation and endStation as input. Retrieve the average travel time from the travelTime hash table using the startStation and endStation.

5. Return the average travel time.

Code:

C++ code to solve this problem is given below:

class UndergroundSystem {
private:
unordered_map> checkIn;
unordered_map, pair\> travelTime;
public:
UndergroundSystem() {
checkIn.clear();
travelTime.clear();
}

void checkIn(int id, string stationName, int t) {
    checkIn[id] = {stationName, t};
}

void checkOut(int id, string stationName, int t) {
    auto& checkInData = checkIn[id];
    string& startStation = checkInData.first;
    int& startTime = checkInData.second;
    int travelDuration = t - startTime;
    auto& travelTimeData = travelTime[{startStation, stationName}];
    travelTimeData.first += travelDuration;
    travelTimeData.second++;
}

double getAverageTime(string startStation, string endStation) {
    auto& travelTimeData = travelTime[{startStation, endStation}];
    return static_cast<double>(travelTimeData.first) / travelTimeData.second;
}

};

Time Complexity:

• The checkIn() method takes O(1) time complexity to check in a passenger.
• The checkOut() method takes O(1) time complexity to check out a passenger and calculates the travel duration.
• The getAverageTime() method takes O(1) time complexity to retrieve the average travel time from the nested hash table.

Therefore, the overall time complexity of this solution is O(1).

Step by Step Implementation For Design Underground System

Design an underground system that allows a customer to check in at any time and check out at any time.

The customer can choose any stationX and stationY that are directly connected by a path.

The system should charge the customer the length of the path between stationX and stationY multiplied by the price per meter.

The system should also keep track of the number of times each customer has used the system and the total amount of money the customer has spent.

class Station {
 
    // name of the station
    String name;
 
    // map of all the destinations reachable from this station and the price per meter to get there
    HashMap destinations;
 
    public Station(String name) {
        this.name = name;
        this.destinations = new HashMap<>();
    }
 
    // add a new destination reachable from this station
    // with the given price per meter
    public void addDestination(String destination, int price) {
        this.destinations.put(destination, price);
    }
 
    // get the price per meter to reach the given destination
    // from this station
    public int getPrice(String destination) {
        return this.destinations.get(destination);
    }
}
 
class Customer {
 
    // name of the customer
    String name;
 
    // total amount of money spent using the underground system
    int totalMoneySpent;
 
    // number of trips made using the underground system
    int numTrips;
 
    public Customer(String name) {
        this.name = name;
        this.totalMoneySpent = 0;
        this.numTrips = 0;
    }
 
    // add the given amount of money to the total money spent
    public void addMoneySpent(int amount) {
        this.totalMoneySpent += amount;
    }
 
    // increment the number of trips made
    public void incrementNumTrips() {
        this.numTrips++;
    }
}
 
public class UndergroundSystem {
 
    // map of all the stations in the underground system
    // mapped by their name
    HashMap stations;
 
    // map of all the customers in the underground system
    // mapped by their name
    HashMap customers;
 
    public UndergroundSystem() {
        this.stations = new HashMap<>();
        this.customers = new HashMap<>();
    }
 
    // check in the customer at the given station
    public void checkIn(String name, String stationName, int t) {
        // get the customer from the map or create a new one
        Customer customer = this.customers.getOrDefault(name, new Customer(name));
 
        // get the station from the map or create a new one
        Station station = this.stations.getOrDefault(stationName, new Station(stationName));
 
        // add the customer to the station's list of customers
        station.addCustomer(customer);
 
        // update the customer's check in time
        customer.setCheckInTime(t);
    }
 
    // check out the customer at the given station
    public void checkOut(String name, String stationName, int t) {
        // get the customer from the map
        Customer customer = this.customers.get(name);
 
        // get the station from the map
        Station station = this.stations.get(stationName);
 
        // remove the customer from the station's list of customers
        station.removeCustomer(customer);
 
        // update the customer's total money spent and number of trips
        customer.addMoneySpent((t - customer.getCheckInTime()) * station.getPrice(stationName));
        customer.incrementNumTrips();
    }
 
    // get the average time a customer spends between check in and check out
    // at the given station
    public double getAverageTime(String stationName) {
        // get the station from the map
        Station station = this.stations.get(stationName);
 
        // return the average time
        return station.getAverageTime();
    }
 
    // get the average amount of money a customer spends when using the
    // underground system
    public double getAverageMoneySpent(String name) {
        // get the customer from the map
        Customer customer = this.customers.get(name);
 
        // return the average amount of money spent
        return customer.getAverageMoneySpent();
    }
}

class UndergroundSystem:

    def __init__(self):
        self.station_map = {}
        self.trip_map = {}
        

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.station_map[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        in_station, in_time = self.station_map[id]
        trip_key = (in_station, stationName)
        if trip_key not in self.trip_map:
            self.trip_map[trip_key] = []
        self.trip_map[trip_key].append((in_time, t))

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        trip_key = (startStation, endStation)
        times = self.trip_map[trip_key]
        total_time = 0
        for in_time, out_time in times:
            total_time += out_time - in_time
        return total_time / len(times)

var UndergroundSystem = function() {
    // Create a map to store all the stations 
    this.stationMap = new Map(); 
};

/** 
 * @param {string} stationName 
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkIn = function(stationName, t) {
    // Store the arrival time for the customer 
    this.stationMap.set(stationName, t); 
};

/** 
 * @param {string} stationName 
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkOut = function(stationName, t) {
    // Get the arrival time for the customer 
    let arrivalTime = this.stationMap.get(stationName); 
    
    // Calculate the travel time 
    let travelTime = t - arrivalTime; 
    
    // Store the travel time in the map 
    if (this.stationMap.has(stationName + t)) {
        let currList = this.stationMap.get(stationName + t); 
        currList.push(travelTime); 
        this.stationMap.set(stationName + t, currList); 
    } else {
        let list = []; 
        list.push(travelTime); 
        this.stationMap.set(stationName + t, list); 
    }
};

/** 
 * @param {string} startStation 
 * @param {string} endStation 
 * @return {number}
 */
UndergroundSystem.prototype.getAverageTime = function(startStation, endStation) {
    // Get the list of travel times 
    let list = this.stationMap.get(startStation + endStation); 
    
    // Calculate the average travel time 
    let sum = 0; 
    for (let i = 0; i < list.length; i++) {
        sum += list[i]; 
    }
    
    return sum / list.length; 
};

/** 
 * Your UndergroundSystem object will be instantiated and called as such:
 * var obj = new UndergroundSystem()
 * obj.checkIn(stationName,t)
 * obj.checkOut(stationName,t)
 * var param_3 = obj.getAverageTime(startStation,endStation)
 */

class UndergroundSystem {
public:
    UndergroundSystem() {
        
    }
    
    void checkIn(int id, string stationName, int t) {
        check_ins[id] = {stationName, t};
    }
    
    void checkOut(int id, string stationName, int t) {
        auto check_in = check_ins[id];
        string route = check_in.first + "_" + stationName;
        int &travel_time = travel_times[route];
        int &count = counts[route];
        travel_time = (travel_time * count + t - check_in.second) / (count + 1);
        ++count;
    }
    
    double getAverageTime(string startStation, string endStation) {
        string route = startStation + "_" + endStation;
        return travel_times[route];
    }
private:
    unordered_map> check_ins;
    unordered_map travel_times;
    unordered_map counts;
};

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem* obj = new UndergroundSystem();
 * obj->checkIn(id,stationName,t);
 * obj->checkOut(id,stationName,t);
 * double param_3 = obj->getAverageTime(startStation,endStation);
 */

public class UndergroundSystem
{
    Dictionary station;
    Dictionary journey;
    public UndergroundSystem()
    {
        station = new Dictionary();
        journey = new Dictionary();
    }
    
    public void CheckIn(int id, string stationName, int t)
    {
        station.Add(id, stationName);
    }
    
    public void CheckOut(int id, string stationName, int t)
    {
        string start = station[id];
        station.Remove(id);
        string key = start + "," + stationName;
        if(!journey.ContainsKey(key))
            journey.Add(key, new int[2] {t, 1});
        else
        {
            journey[key][0] += t;
            journey[key][1] += 1;
        }
    }
    
    public double GetAverageTime(string startStation, string endStation)
    {
        string key = startStation + "," + endStation;
        return (double)journey[key][0] / journey[key][1];
    }
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem obj = new UndergroundSystem();
 * obj.CheckIn(id,stationName,t);
 * obj.CheckOut(id,stationName,t);
 * double param_3 = obj.GetAverageTime(startStation,endStation);
 */