Leetcode.com problem 1396: Design Underground System

James S. Plank

• Problem Statement.
• Success Rate (as of May, 2023): 74.0%
• This is a "medium" problem.

• tests.sh: A testing script
• answers.txt: Correct output to the testing script. My program takes a little under two seconds on this script.

• A skeleton with my main() that you can use to test your answer.

In case Leetcode's servers are down

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

• You are monitoring a railway system.
• In this system, users, who have integer id's, may check in to a railway station, and then check out of a railway station. They do so with the checkIn() and checkOut methods.
• When they check in or out, the specify the station name, and the time of checking in or checking out.
• When they check out, you need to figure out the station for which they last checked in, and keep track of the time.
• getAverageTime() is called with a starting station and an ending station. You need to calculate the average time for all users that checked into the starting station, and then checked out of the ending station.
• id and t are integers between 1 and 1,000,000.
• The station names are strings of digits, and uppercase and lowercase letters. These strings are 10 characters or shorter.
• Each test case will have a maximum of 20,000 method calls.
• The method calls will be in chronological order, and there will never be a checkOut() call without a corresponding checkIn() call at a previous time.

• "I" id station time -- calls checkIn()
• "O" id station time -- calls checkOut()
• "A" start-station end-station -- calls getAverageTime() and prints the return value.

UNIX> cat input-1.txt
I 45 Leyton 3
I 32 Paradise 8
I 27 Leyton 10
O 45 Waterloo 15
O 27 Waterloo 20
O 32 Cambridge 22
A Paradise Cambridge
A Leyton Waterloo
I 10 Leyton 24
A Leyton Waterloo
O 10 Waterloo 38
A Leyton Waterloo
UNIX> ./a.out < input-1.txt
14
11
11
12
UNIX> cat input-2.txt
I 10 Leyton 3
O 10 Paradise 8
A Leyton Paradise
I 5 Leyton 10
O 5 Paradise 16
A Leyton Paradise
I 2 Leyton 21
O 2 Paradise 30
A Leyton Paradise

UNIX> ./a.out < input-2.txt
5
5.5
6.66667
UNIX> 

Hints

1. A data structure that keeps track of the most recent checkin() for each user.
2. A data strcuture that keeps track of information to calculate average times for each (ordered) pair of station.

In checkOut(), you find the user's most recent check-in (which is guaranteed to exist, so says the problem writeup), and calculate the time duration from check-in to check-out, and add that information to the second data structure, keyed on the combination of starting station/ending station.

Lets's walk through example one, just to make it explicit what we're storing:

Ok -- now that we know what we're storing, let's think about the best way to store it:

• Data structure 1: Since we're doing storage and retrieval, and not sorting, we should use an unordered_map, whose key is the user id, and whose val is a string-integer pair. That lets us hold the id, station and time in a single map entry.

• Data structure 2: Once again, we're doing storage and retrival, and not sorting. So we again use an unordered_map, whose key is a string with the starting and ending station, and whose val is a double-integer pair. The double is the sum of durations, and the integer is the number of durations. From those, you may calculate the average. I know in the table above, it looked like I was storing the values in a vector -- that was just to make the table clear. You're much better off from a time and space perspective if you simply store the total and number in the unordered_map.

unordered_map <int, pair <int, string> > Checkins;
unordered_map <string, pair <double, int> > Duration_Info;

I didn't make the total an integer, because 1,000,000 * 20,000 can exceed an integer. Also, you should make sure that the starting-station/ending-station string has an "illegal" character separating the two stations (like a hyphen). If you just concatenate the stations, you can get into trouble with something like:

I 1 Fred 0
I 2 FredFred 1
O 1 FredFred 2
O 2 Fred 3