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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Underground System

Number: 1512

Difficulty: Medium

Paid? No

Companies: Bloomberg, Goldman Sachs, Amazon

Problem Description

Design an underground railway system that tracks customer travel times between different stations. Implement a class with three methods: checkIn to record a customer's starting station and time, checkOut to record their destination and check-out time, and getAverageTime to return the average travel time between two specific stations based on all recorded trips.

Key Insights

  • Use a hash map to store check-in data for each customer.
  • Use another hash map with a composite key representing the journey (startStation, endStation) to store total travel time and trip counts.
  • Upon check out, compute the travel time and update the journey data accordingly.
  • Return the average travel time by dividing the total time by the number of trips for the queried journey.

Space and Time Complexity

Time Complexity: O(1) for checkIn, checkOut, and getAverageTime operations. Space Complexity: O(n), where n is the number of active check-ins and distinct station pairs recorded.

Solution

Maintain two hash maps:

  1. The first map (checkIns) records customer check-in information (station name and time) keyed by customer id.
  2. The second map (journeys) aggregates the total travel time and the count of trips for each journey, using a composite key of startStation and endStation. When a customer checks in, store their information in checkIns. When they check out, retrieve and remove their check-in data, calculate the travel time, and update the corresponding journey's total time and count. The average time is computed by dividing the total time by the number of trips.

Code Solutions

Here are implementations in Python, JavaScript, C++, and Java with line-by-line comments:

class UndergroundSystem:
    def __init__(self):
        # Dictionary to store active check-ins: id -> (stationName, checkInTime)
        self.checkIns = {}
        # Dictionary to store journey information: (startStation, endStation) -> (totalTime, count)
        self.journeys = {}
    
    def checkIn(self, id: int, stationName: str, t: int) -> None:
        # Record customer's check-in data
        self.checkIns[id] = (stationName, t)
    
    def checkOut(self, id: int, stationName: str, t: int) -> None:
        # Retrieve check-in details and remove the entry from checkIns
        startStation, startTime = self.checkIns.pop(id)
        # Compute travel time
        duration = t - startTime
        key = (startStation, stationName)
        # Update journey data with new duration and increment trip count
        if key in self.journeys:
            totalTime, count = self.journeys[key]
            self.journeys[key] = (totalTime + duration, count + 1)
        else:
            self.journeys[key] = (duration, 1)
    
    def getAverageTime(self, startStation: str, endStation: str) -> float:
        # Retrieve total time and number of trips for the journey
        totalTime, count = self.journeys[(startStation, endStation)]
        return totalTime / count
← Back to All Questions