# 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
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

// 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.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
```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)
{
}

public void CheckOut(int id, string stationName, int t)
{
string start = station[id];
station.Remove(id);
string key = start + "," + stationName;
if(!journey.ContainsKey(key))
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);
*/```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]