We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Underground System

Difficulty: Medium

Problem Description

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

  • void checkIn(int id, string stationName, int t)

    • A customer with a card ID equal to id, checks in at the station stationName at time t.
    • A customer can only be checked into one place at a time.

  • void checkOut(int id, string stationName, int t)

    • A customer with a card ID equal to id, checks out from the station stationName at time t.

  • double getAverageTime(string startStation, string endStation)

    • Returns the average time it takes to travel from startStation to endStation.
    • The average time is computed from all the previous traveling times from startStation to endStation that happened directly.
    • The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
    • There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

Key Insights

  • Use a hash table to map customer IDs to their check-in station and time.
  • Use another hash table to track the total travel time and count of trips between pairs of stations.
  • Ensure that when checking out, the travel time is calculated and stored for future average calculations.
  • The average time can be computed simply by dividing the total travel time by the count of trips.

Space and Time Complexity

Time Complexity:

  • checkIn: O(1)
  • checkOut: O(1)
  • getAverageTime: O(1)

Space Complexity:

  • O(N) where N is the number of unique station pairs and customers checked in at any given time.

Solution

To solve this problem, we will utilize two hash tables:

  1. checkInData to store the check-in information using the customer ID as the key.
  2. travelTimes to store the total travel time and count of trips for each pair of stations.

When a customer checks in, we will record their station and time. Upon checkout, we will calculate the travel time, update our total time and increment the count for that station pair. The average is then easily computed when requested.

Code Solutions

class UndergroundSystem:
    def __init__(self):
        self.checkInData = {}  # Maps id to (stationName, checkInTime)
        self.travelTimes = {}   # Maps (startStation, endStation) -> (totalTime, count)

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

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        startStation, startTime = self.checkInData.pop(id)
        travelTime = t - startTime
        if (startStation, stationName) not in self.travelTimes:
            self.travelTimes[(startStation, stationName)] = (0, 0)
        totalTime, count = self.travelTimes[(startStation, stationName)]
        self.travelTimes[(startStation, stationName)] = (totalTime + travelTime, count + 1)

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        totalTime, count = self.travelTimes[(startStation, endStation)]
        return totalTime / count
← Back to All Questions