Problem 40.13 · Designing Data StructuresMedium

Design Underground System

PatternCombine Structures to Design Hash Map Lookup (Complement)

What it teaches: Two maps: who is currently travelling (id → start), and running totals per route ("from→to" → sum and count).

Practise it on judges as “Design Underground System”.

In plain words

A metro card system notes when you tap in and where, and when you tap out and where. The company wants to know: on average, how long does a trip from station A to station B take?

Build checkIn(id, station, t), checkOut(id, station, t) and getAverageTime(start, end), the average of all completed trips from start to end.

The problem

Design UndergroundSystem. A customer checks in at one station and later out at another. getAverageTime returns the average duration of all completed trips from startStation to endStation (there's at least one).

Example 1

Input: checkIn(10, Leyton, 3), checkOut(10, Paradise, 8), getAverageTime(Leyton, Paradise)
Output: 5.0

Constraints

Up to 2 × 10⁴ calls
Times are increasing for each customer

Pattern clues in the wording

→ Pair two events by id
→ Running average per key

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

UndergroundSystem · starter

import java.util.*;

class UndergroundSystem {
    public UndergroundSystem() {}
    public void checkIn(int id, String stationName, int t) {}
    public void checkOut(int id, String stationName, int t) {}
    public double getAverageTime(String startStation, String endStation) { return 0.0; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"] args = [[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]	[null,null,null,5,null,null,5.5,null,null,6.66667]

From slow to fast

Approaches

1. Open trips + route totals · O(1) per call

Open trips + route totals

Time O(1) per call Space O(customers + routes)

open: id → {station, time}. routes: "A->B" → {total time, count}. checkOut closes the trip and updates totals; the average is total / count.

▶ Dry run: Open trips + totals per routecheckIn(10, Leyton, 3), checkOut(10, Paradise, 8), getAverageTime(Leyton, Paradise)

open(map)

10: (Leyton, 3)

routes {total, trips}(map)

empty

Step 1/3checkIn: remember where and when customer 10 started.

Approach 1

import java.util.*;

class UndergroundSystem {
    private record Trip(String station, int time) {}
    private final Map<Integer, Trip> open = new HashMap<>();
    private final Map<String, long[]> routes = new HashMap<>();     // {total time, trips}

    public UndergroundSystem() {}

    public void checkIn(int id, String stationName, int t) { open.put(id, new Trip(stationName, t)); }

    public void checkOut(int id, String stationName, int t) {
        Trip trip = open.remove(id);
        long[] r = routes.computeIfAbsent(trip.station() + "->" + stationName, k -> new long[2]);
        r[0] += t - trip.time();
        r[1]++;
    }

    public double getAverageTime(String startStation, String endStation) {
        long[] r = routes.get(startStation + "->" + endStation);
        return (double) r[0] / r[1];
    }
}

Verdict: Never stores the full trip history.

Before you submit

Edge cases and common mistakes

Test these inputs

The same customer making several trips
Routes in opposite directions are different

Mistakes people make

Using a key like start + end without a separator ("ab"+"c" equals "a"+"bc").

Interview

Follow-up questions

What changes if average times are needed per hour of day?

Command Palette

The problem

Approaches

Open trips + route totals

Edge cases and common mistakes

Follow-up questions