1396. Design Underground System

MediumDesignHash TableString
Leetcode Link

Problem Description

In this problem, we have to implement a class UndergroundSystem that simulates the tracking system for an underground railway company. This class will be responsible for keeping a log of customer check-ins and check-outs at different stations and computing the average travel time between any two given stations. There are three main operations that the UndergroundSystem should support:

  1. checkIn(id, stationName, t): When a customer with a unique card ID checks in at a given station at a specific time.
  2. checkOut(id, stationName, t): When a customer with the same card ID checks out from a given station at a later time than they checked in.
  3. getAverageTime(startStation, endStation): Calculate and return the average time taken for all trips from the startStation to the endStation. Note that the times from startStation to endStation and endStation to startStation are calculated separately, as the travel time between two stations may vary depending on the direction.

It is important to note that a customer can only be checked into one station at a time and all travel times are calculated directly between a start and an end station without considering intermediate steps.

Intuition

The key to solving this problem lies in effectively tracking the travel time of each customer from check-in to check-out and then using this information to calculate the average time. This can be done by associating each customer's check-in information (which includes the check-in time and check-in station) with their unique ID. When the customer checks out, we can then use their ID to retrieve the check-in data, calculate the total travel time, and record this information for the pair of stations involved.

For storing customer-specific data, we can use a dictionary that maps a customer ID to a tuple containing the check-in time and station. We maintain another dictionary to keep a cumulative sum of all travel times and the number counts between each unique pair of stations. The key for this dictionary is a tuple consisting of the startStation and endStation, and the value is another tuple containing the sum of all travel times and the total number of trips made between those stations.

When computing the average time, we need to retrieve the travel time sum and count for the station pair from our dictionary and divide the accumulated travel time by the total trip count for the given pair of stations.

The given solution is efficient because it only involves dictionary lookups, insertions, and basic arithmetic operations, all of which occur in constant time with respect to the number of customers and trips.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The solution approach involves implementing three essential methods in the UndergroundSystem class, each corresponding to the operations given in the problem description. Let's break down each part of the implementation:

Data Structures Used

  • The first data structure is a dictionary named self.ts which serves as a temporary storage for each customer's check-in information. This dictionary maps each customer's ID to a tuple that contains the check-in time and station name.
  • The second data structure is a dictionary named self.d which is used to maintain the total travel time and trip count between station pairs. It maps a tuple of (startStation, endStation) to another tuple (totalTime, tripCount).

Implementation of Methods

  • __init__(self): This method initializes both dictionaries. self.ts will hold check-in data and self.d will hold the accumulated travel data.

  • checkIn(self, id: int, stationName: str, t: int): When a customer checks in,

    • The customer's ID, along with the check-in time and station name, is stored in self.ts.

  • checkOut(self, id: int, stationName: str, t: int): When the same customer checks out,

    • The method retrieves the stored check-in information using the ID from self.ts.
    • It then calculates the travel time by subtracting the check-in time from the check-out time.
    • The method looks up in self.d if there is an existing entry for that station pair.
    • If the station pair exists, it updates the cumulative travel time and increments the trip count; otherwise, it initializes them.
    • Finally, it removes the check-in record from self.ts as it is no longer needed after check-out.

  • getAverageTime(self, startStation: str, endStation: str): To obtain the average travel time between a start and end station,

    • It retrieves the total travel time and trip count from self.d for the given station pair tuple.
    • The average time is then calculated by dividing the total travel time by the trip count.

Algorithm Analysis

The solution makes efficient use of hash tables (dictionaries in Python) to achieve constant time complexity (O(1)) operations for check-ins, check-outs, and average time retrieval.

  • The check-in operation only involves inserting the ID and corresponding tuple into the self.ts dictionary.
  • The check-out operation involves simple arithmetic and dictionary updates, which are also O(1) operations.
  • The getAverageTime operation is a straightforward dictionary lookup and division to compute the average.

The class is designed to handle the real-time entry and exit logs of customers while ensuring that the calculation of the average time remains efficient regardless of the number of entries made or the frequency of access.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's illustrate the solution approach with an example:

Suppose we have an UndergroundSystem object and the following sequence of events occurs:

  1. Customer with ID 1 checks in at "StationA" at time 5.
  2. Customer with ID 2 checks in at "StationB" at time 10.
  3. Customer with ID 1 checks out at "StationB" at time 15.
  4. Customer with ID 2 checks out at "StationA" at time 20.
  5. We request the average time from "StationA" to "StationB".
  6. We request the average time from "StationB" to "StationA".

Let's walk through these steps using the proposed solution:

Step 1: Check-in Customer ID 1

  • checkIn(1, "StationA", 5): The checkIn method is called; customer ID 1 checks in at "StationA" at time 5.
  • self.ts dictionary after this operation: {1: ("StationA", 5)}

Step 2: Check-in Customer ID 2

  • checkIn(2, "StationB", 10): The checkIn method is called; customer ID 2 checks in at "StationB" at time 10.
  • self.ts dictionary after this operation: {1: ("StationA", 5), 2: ("StationB", 10)}

Step 3: Check-out Customer ID 1

  • checkOut(1, "StationB", 15): The check-out method is called for customer ID 1 at "StationB" at time 15.
  • The system retrieves the check-in data for ID 1 from self.ts: ("StationA", 5).
  • It calculates the travel time: 15 - 5 = 10.
  • Since this is the first trip between "StationA" and "StationB", it initializes the entry in self.d: {("StationA", "StationB"): (10, 1)}.
  • The check-in record for ID 1 is removed from self.ts.

Step 4: Check-out Customer ID 2

  • checkOut(2, "StationA", 20): The check-out method is called for customer ID 2 at "StationA" at time 20.
  • The system retrieves the check-in data for ID 2 from self.ts: ("StationB", 10).
  • It calculates the travel time: 20 - 10 = 10.
  • Since this is the first trip between "StationB" and "StationA", it initializes the entry in self.d: {("StationB", "StationA"): (10, 1)} alongside the previous entry.
  • The check-in record for ID 2 is removed from self.ts.

Step 5: Get Average Time from "StationA" to "StationB"

  • getAverageTime("StationA", "StationB"): The getAverageTime method is called for the station pair "StationA" to "StationB".
  • It looks up self.d and finds the total travel time and trip count: (10, 1).
  • It calculates the average time: 10 / 1 = 10.
  • The method returns 10 as the average travel time from "StationA" to "StationB".

Step 6: Get Average Time from "StationB" to "StationA"

  • getAverageTime("StationB", "StationA"): The getAverageTime method is called for the station pair "StationB" to "StationA".
  • It looks up self.d and finds the total travel time and trip count: (10, 1).
  • It calculates the average time: 10 / 1 = 10.
  • The method returns 10 as the average travel time from "StationB" to "StationA".

These steps demonstrate how the UndergroundSystem class functions and how it computes and updates the travel information for each trip. The example here clearly shows how each method operates and manipulates the internal data structures to return the required results.

Solution Implementation

1class UndergroundSystem:
2    def __init__(self):
3        self.travel_times = {}  # Stores travel times for each passenger id: {id: (start_time, start_station)}
4        self.journey_data = {}  # Stores total time and count for each journey: {(start_station, end_station): (total_time, trip_count)}
5
6    def checkIn(self, passenger_id: int, start_station: str, start_time: int) -> None:
7        # When a passenger checks in, record their start time and station
8        self.travel_times[passenger_id] = (start_time, start_station)
9
10    def checkOut(self, passenger_id: int, end_station: str, end_time: int) -> None:
11        # When a passenger checks out, compute the journey time and update journey data
12        start_time, start_station = self.travel_times[passenger_id]
13        journey_time = end_time - start_time
14       
15        # Retrieve the existing total time and trip count for the journey, if any
16        total_time, trip_count = self.journey_data.get((start_station, end_station), (0, 0))
17
18        # Update the journey data with the new total time and increased trip count
19        self.journey_data[(start_station, end_station)] = (total_time + journey_time, trip_count + 1)
20
21        # Remove passenger's check-in data as it is no longer needed
22        del self.travel_times[passenger_id]
23
24    def getAverageTime(self, start_station: str, end_station: str) -> float:
25        # Calculate the average journey time for a start and end station
26        total_time, trip_count = self.journey_data[(start_station, end_station)]
27        return total_time / trip_count  # Return the average time
28
29# Example usage of the UndergroundSystem:
30# underground_system = UndergroundSystem()
31# underground_system.checkIn(passenger_id, start_station, start_time)
32# underground_system.checkOut(passenger_id, end_station, end_time)
33# average_time = underground_system.getAverageTime(start_station, end_station)
34
1import java.util.HashMap;
2import java.util.Map;
3
4class UndergroundSystem {
5
6    // Store the check-in time for each id
7    private Map<Integer, Integer> checkInTimeMap = new HashMap<>();
8  
9    // Store the check-in station name for each id
10    private Map<Integer, String> checkInStationMap = new HashMap<>();
11  
12    // Store the total duration and total trips for each station pair
13    private Map<String, int[]> travelInfoMap = new HashMap<>();
14
15    // Constructor for the UndergroundSystem
16    public UndergroundSystem() {
17    }
18
19    // Method to record a customer's check-in event
20    public void checkIn(int id, String stationName, int t) {
21        // Record the check-in time
22        checkInTimeMap.put(id, t);
23        // Record the check-in station name
24        checkInStationMap.put(id, stationName);
25    }
26
27    // Method to record a customer's check-out event
28    public void checkOut(int id, String stationName, int t) {
29        // Generate a unique key for the start and end station pair
30        String routeKey = checkInStationMap.get(id) + "-" + stationName;
31      
32        // Retrieve the travel information for this station pair, or create new if it doesn't exist
33        int[] travelData = travelInfoMap.getOrDefault(routeKey, new int[2]);
34      
35        // Update the total duration for this station pair
36        travelData[0] += t - checkInTimeMap.get(id);
37      
38        // Update the total number of trips for this station pair
39        travelData[1]++;
40      
41        // Store the updated travel data
42        travelInfoMap.put(routeKey, travelData);
43    }
44
45    // Method to get the average travel time between a start and end station
46    public double getAverageTime(String startStation, String endStation) {
47        // Generate the unique key for the station pair
48        String routeKey = startStation + "-" + endStation;
49      
50        // Retrieve the travel information for this station pair
51        int[] travelData = travelInfoMap.get(routeKey);
52      
53        // Calculate and return the average time
54        return (double) travelData[0] / travelData[1];
55    }
56}
57
58/**
59 * The UndergroundSystem object will be instantiated and used like this:
60 * UndergroundSystem obj = new UndergroundSystem();
61 * obj.checkIn(id, stationName, t);
62 * obj.checkOut(id, stationName, t);
63 * double averageTime = obj.getAverageTime(startStation, endStation);
64 */
65
1#include <unordered_map>
2#include <string>
3
4using namespace std;
5
6// Defining a class to represent the Underground system
7class UndergroundSystem {
8public:
9    // Constructor (no parameters since nothing is being initialized)
10    UndergroundSystem() {
11    }
12
13    // Function to record when a user checks into a station
14    void checkIn(int id, string stationName, int time) {
15        // Storing the check-in information with the user's id as the key
16        checkInData[id] = {stationName, time};
17    }
18
19    // Function to record when a user checks out from a station
20    void checkOut(int id, string stationName, int time) {
21        // Extracting the check-in data for this user (the station they checked in at and the time they checked in)
22        auto& [checkInStation, checkInTime] = checkInData[id];
23        // Creating a route key by concatenating the check-in and check-out station names
24        string routeKey = checkInStation + "-" + stationName;
25        // Extract current total time and count for this route if exists. Initialize to {0, 0} if none.
26        auto& [totalTime, tripCount] = journeyData[routeKey];
27        // Update the total time and count for this route
28        journeyData[routeKey] = {totalTime + (time - checkInTime), tripCount + 1};
29    }
30
31    // Function to calculate the average travel time for a specific journey
32    double getAverageTime(string startStation, string endStation) {
33        // Obtain the total time and count for the requested route
34        auto& [totalTime, tripCount] = journeyData[startStation + "-" + endStation];
35        // Calculate and return the average time
36        return static_cast<double>(totalTime) / tripCount;
37    }
38
39private:
40    // Data structure to store check-in data, using the user's id as the key
41    unordered_map<int, pair<string, int>> checkInData;
42    // Data structure to store journey data (total time and trip count) for each route
43    unordered_map<string, pair<int, int>> journeyData;
44};
45
46/*
47* Your UndergroundSystem object will be instantiated and called as such:
48* UndergroundSystem* obj = new UndergroundSystem();
49* obj->checkIn(id, stationName, time);
50* obj->checkOut(id, stationName, time);
51* double avgTime = obj->getAverageTime(startStation, endStation);
52*/
53
1// Importing necessary functionality for hashing
2import { HashMap } from 'hashmap';
3
4// Structure to hold check-in data
5interface CheckInData {
6  stationName: string;
7  time: number;
8}
9
10// Structure to hold journey data
11interface JourneyData {
12  totalTime: number;
13  tripCount: number;
14}
15
16// Global maps to hold check-in and journey data
17const checkInDataMap: HashMap<number, CheckInData> = new HashMap();
18const journeyDataMap: HashMap<string, JourneyData> = new HashMap();
19
20/**
21 * Records when a user checks into a station.
22 * @param {number} id - The unique identifier of the user.
23 * @param {string} stationName - The name of the station where the user checked in.
24 * @param {number} time - The check-in time.
25 */
26function checkIn(id: number, stationName: string, time: number): void {
27  checkInDataMap.set(id, {stationName, time});
28}
29
30/**
31 * Records when a user checks out from a station.
32 * @param {number} id - The unique identifier of the user.
33 * @param {string} stationName - The name of the station where the user checked out.
34 * @param {number} time - The check-out time.
35 */
36function checkOut(id: number, stationName: string, time: number): void {
37  const checkInData = checkInDataMap.get(id);
38  if (checkInData) {
39    const routeKey: string = `${checkInData.stationName}-${stationName}`;
40    let journeyData = journeyDataMap.get(routeKey) || { totalTime: 0, tripCount: 0 };
41
42    journeyData = {
43      totalTime: journeyData.totalTime + (time - checkInData.time),
44      tripCount: journeyData.tripCount + 1
45    };
46
47    journeyDataMap.set(routeKey, journeyData);
48  }
49}
50
51/**
52 * Calculates the average travel time for a specific journey.
53 * @param {string} startStation - The starting station of the journey.
54 * @param {string} endStation - The ending station of the journey.
55 * @returns {number} Average travel time for the journey.
56 */
57function getAverageTime(startStation: string, endStation: string): number {
58  const routeKey: string = `${startStation}-${endStation}`;
59  const journeyData = journeyDataMap.get(routeKey);
60  if (!journeyData) throw new Error('No journey data found for this route.');
61
62  return journeyData.totalTime / journeyData.tripCount;
63}
64
65// Usage Example:
66// checkIn(1, 'A', 10);
67// checkOut(1, 'B', 20);
68// const avgTime = getAverageTime('A', 'B'); // This would yield 10
69
Not Sure What to Study? Take the 2-min Quiz：

How many ways can you arrange the three letters A, B and C?

Time and Space Complexity

Time Complexity

  • The __init__ method only initializes two dictionaries, which is an O(1) operation.
  • The checkIn method performs a single assignment to insert an (id, stationName) pair with the timestamp t into the ts dictionary, which is an O(1) operation.
  • The checkOut method performs a lookup and an update in ts dictionary which is an O(1) operation, and an update in d dictionary to keep track of the total travel time and count for a specific route, which is also an O(1) operation.
  • The getAverageTime method performs a single lookup in the d dictionary and a division to calculate the average time, which is an O(1) operation.

Given these points, all the methods (checkIn, checkOut, and getAverageTime) have a time complexity of O(1).

Space Complexity

  • The space complexity of the class UndergroundSystem is determined by the space used to store the check-ins in ts and the travel times and counts in d.
  • For ts, in the worst case, it stores entries for all unique check-in IDs. If there are n different users who have checked in, then ts will have n entries, giving a space complexity of O(n).
  • For d, in the worst case, it stores entries for each unique pair of start and end stations. If there are s stations, then in the worst case, there could be s^2 pairs of routes, giving a space complexity of O(s^2).

Therefore, the overall space complexity of the system is O(n + s^2), considering both ts and d.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫