Design Underground System Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg
Design HashMap StringViews 1953

Design Underground System Leetcode Solution

Problem Statement

The Design Underground System LeetCode Solution – “Design Underground System” asks you to design a railway system to keep track of customer travel times between two stations. It is needed to calculate the average time it takes to travel from one station to another.

We need to implement the UndergroundSystem class:

  • Checkin: A customer with a card ID equal to id, checks in at the station stationName at time t.
  • Checkout: A customer with a card ID equal to id, checks out from the station stationName at time t.
  • GetAverageTime: Returns the average time it takes to travel from startStation to endStation. The average time is calculated from all the previous traveling times from start station to end station that had happened directly.

Example:

Input:  ["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]
Output: [null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation:

  • Checkin at (45, Leyton, 3). Checkin at (32, Paradise, 8), Checkin at (32, Paradise, 8).
  • Checkout at (45, Waterloo, 15).
  • Checkout at (27, Waterloo, 20).
  • Checkout(32, Cambridge, 22).
  • Average Time(Paradise, Cambridge) = 14/1 = 14.
  • Average Time(Leyton, Waterloo) = (10+12)/2 = 11.
  • Average Time(Leyton, Waterloo) = 11.
  • Checkout(10, Waterloo, 38).
  • Average Time(Leyton, Waterloo) = (10+12+14)/3 = 12.

Approach

Idea:

  1. The main idea to solve this problem is to use a hashmap.
  2. Maintain two different hashmaps, one for check-ins and the other for routes.
  3. Now, for each check-in, insert the id with the station name and current time.
  4. Also, for each check-out, erase the entry for the check-in hashmap. Also, insert the route formed from the check-in station to the check-out station in the route hashmap.
  5. Calculate the average time with the help of count and sum entries of the route hashmap.

Code

Design Underground System Leetcode C++ Solution:

class UndergroundSystem {
public:
    unordered_map<int, pair<string, int>> checkins;
    unordered_map<string, pair<int, int>> routes;
    void checkIn(int id, string stationName, int t) {
        checkins[id] = {stationName, t};
    }
    void checkOut(int id, string stationName, int t) {
        auto [stn, start] = checkins[id];
        checkins.erase(id);
        string route = stn + "," + stationName;
        routes[route].first++, routes[route].second += t - start;
    }
    double getAverageTime(string startStation, string endStation) {
        auto& [count, sum] = routes[startStation + "," + endStation];
        return (double)sum / count;
    }
};

Design Underground System Leetcode Java Solution:

class UndergroundSystem {
    Map<Integer, Pair<String, Integer>> checkins = new HashMap<>();
    Map<Pair<String, String>, int[]> routes = new HashMap<>();
    public void checkIn(int id, String stationName, int t) {
        checkins.put(id, new Pair(stationName, t));
    }
    public void checkOut(int id, String stationName, int t) {
        Pair<String, Integer> cIn = checkins.get(id);
        checkins.remove(id);
        Pair<String, String> route = new Pair(cIn.getKey(), stationName);
        int[] trip = routes.getOrDefault(route, new int[2]);
        trip[0]++;
        trip[1] += t - cIn.getValue();
        routes.put(route, trip);
    }
    public double getAverageTime(String startStation, String endStation) {
        int[] trip = routes.get(new Pair(startStation, endStation));
        return (double)trip[1] / trip[0];
    }
}

Complexity Analysis for Design Underground System Leetcode Solution

Time Complexity

The time complexity of the above code is O(logN) for each function call where N = a maximum number of check-in/check out done.

Space Complexity

The space complexity of the above code is O(N).

Reference https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

Translate »