I am trying to solve LeetCode problem 1396. Design Underground System:
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
UndergroundSystemclass:
void checkIn(int id, string stationName, int t)
- A customer with a card ID equal to
id, checks in at the stationstationNameat timet.- 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 stationstationNameat timet.double getAverageTime(string startStation, string endStation)
- Returns the average time it takes to travel from
startStationtoendStation.- The average time is computed from all the previous traveling times from
startStationtoendStationthat happened directly, meaning a check in atstartStationfollowed by a check out fromendStation.- The time it takes to travel from
startStationtoendStationmay be different from the time it takes to travel fromendStationtostartStation.- There will be at least one customer that has traveled from
startStationtoendStationbeforegetAverageTimeis called.You may assume all calls to the
checkInandcheckOutmethods are consistent. If a customer checks in at timet1then checks out at timet2, thent1<t2. All events happen in chronological order.
For this leetcode problem, I am passing 52/59 test cases, but I am not able to figure out why I am failing the rest. I cannot compare the output between the expected and what I got because LeetCode truncates the large outputs. Can anyone tell me what the issue here might be?
class UndergroundSystem {
HashMap<Integer, LinkedList<String>> map = new HashMap<>(); //holds player id and station names with t time start
HashMap<Integer, LinkedList<String>> cMap = new HashMap<>(); //holds player id and exit station name with t time diff
public UndergroundSystem() {
map = new HashMap<>();
cMap = new HashMap<>();
}
public void checkIn(int id, String stationName, int t) {
if(!map.containsKey(id)) {
LinkedList<String> list = new LinkedList<>();
list.add(stationName);
list.add(Double.toString(t));
map.put(id, list);
}
}
public void checkOut(int id, String stationName, int t) {
//same id then subtract the times
if(map.containsKey(id)) {
LinkedList<String> subList = new LinkedList<>();
subList.add(stationName);
subList.add(Double.toString(Math.abs(Double.parseDouble(map.get(id).get(1)) - t)));
cMap.put(id, subList);
}
}
public double getAverageTime(String startStation, String endStation) {
//first map is going to give us the start station
//second map is going to give us the end station and the time
// LinkedList<String> l1 = new LinkedList<>(map.values());
// LinkedList<String> l2 = new LinkedList<>(cMap.values());
double count = 0;
double sum = 0;
// HashMap<Integer, LinkedList<String>> map1 = map;
// HashMap<Integer, LinkedList<String>> cMap1 = cMap;
for(Integer i: map.keySet()) {
if(map.containsKey(i) && cMap.containsKey(i) && map.get(i).get(0).equals(startStation) && cMap.get(i).get(0).equals(endStation)) {
sum += Double.parseDouble(cMap.get(i).get(1));
count++;
}
}
return count == 0 ? 0 : sum / count;
}
}
/**
* Your UndergroundSystem object will be instantiated and called as such:
* UndergroundSystem obj = new UndergroundSystem();
* obj.checkIn(id,stationName,t);
* obj.checkOut(id,stationName,t);
* double param_3 = obj.getAverageTime(startStation,endStation);
*/
Edit:
If anyone is curious how I fixed it, this is what I did, prolly not the best way but still:
class UndergroundSystem {
HashMap<Integer, LinkedList<String>> checkIns = new HashMap<>();
HashMap<String, int[]> travelTimes = new HashMap<>();
public UndergroundSystem() {}
public void checkIn(int id, String stationName, int t) {
checkIns.put(id, new LinkedList<>(List.of(stationName, Integer.toString(t))));
}
public void checkOut(int id, String stationName, int t) {
if (checkIns.containsKey(id)) {
LinkedList<String> checkInInfo = checkIns.remove(id);
String key = checkInInfo.getFirst() + "," + stationName;
int[] data = travelTimes.getOrDefault(key, new int[]{0, 0});
data[0] += t - Integer.parseInt(checkInInfo.getLast()); // Calculate travel time correctly
data[1]++;
travelTimes.put(key, data);
}
}
public double getAverageTime(String startStation, String endStation) {
String key = startStation + "," + endStation;
int[] data = travelTimes.get(key);
return data != null && data[1] != 0 ? (double) data[0] / data[1] : 0; // Avoid division by zero
}
}
There are several problems in your attempt:
checkIn doesn't do anything if the same id was already used for a previous trip (check-in + check-out).
checkOut takes map.get(id).get(1) without checking that this was the entry of the current trip, which would be the last entry in map.get(id). Now you're always taking the same check-in time for all the trips that the same person makes.
Both checkIn and checkOut create a new list on each call, put the information for one event in it, and then write that list to the relevant map. That means that a map entry will always have a list with the information for exactly one event, never more. There is no code that extends a list that was already present in the map.
getAverageTime never looks any further in the linked lists, and just hopes that the station of the first entry will match. This again means that if the same person (id) makes multiple trips, you'll not be able to report on all those.
Here is a simple test case that fails with your code:
In LeetCode format:
["UndergroundSystem","checkIn","checkOut","checkIn","checkOut","getAverageTime"]
[[],[1,"A",1],[1,"B",2],[1,"B",3],[1,"C",4],["B","C"]]
Or put in code:
UndergroundSystem subway = new UndergroundSystem();
subway.checkIn(1, "A", 1);
subway.checkOut(1, "A", 2);
subway.checkIn(1, "B", 3);
subway.checkOut(1, "B", 4);
System.out.println(subway.getAverageTime("B", "C"));
I would not continue with this data structure; it is not the best choice: it is not efficient to have to look into the linked lists to find the correct pair of stations to return the average travel time. In fact, if we log the travel information at check-out, we don't need a list of all check-ins that a certain id made: they become irrelevant once a trip is completed and we have processed the travel time.
You'll want to structure information in a different way:
For a given id you only need to store the check-in information of the most recent check-in for that card id. There is no need for a linked list. Instead use a pair of station and time.
For a pair of station names you need to keep track of the number of trips and the total accumulated time spent on such trips. This could be a nested map, but since it is given that the station names only have alphanumeric characters, we could use the comma-separated concatenation of two station names (from-to) as the key for a one-dimensional map.
Here is a possible implementation:
class UndergroundSystem {
private class CheckIn {
String startStation;
int startTime;
CheckIn(String stationName, int time) {
startStation = stationName;
startTime = time;
}
}
private class Statistic {
int tripCount = 0;
int totalTravelTime = 0;
void logTrip(int travelTime) {
tripCount++;
totalTravelTime += travelTime;
}
double getAverage() {
return (double) totalTravelTime / tripCount;
}
}
// Per card id: the most recent check-in information
HashMap<Integer, CheckIn> checkIns = new HashMap<>();
// Per pair of stations (concatenated): the overall trip statistics
HashMap<String, Statistic> trips = new HashMap<>();
public void checkIn(int id, String stationName, int time) {
checkIns.put(id, new CheckIn(stationName, time));
}
public void checkOut(int id, String stationName, int time) {
CheckIn checkIn = checkIns.get(id); // There must be a check-in.
String tripName = checkIn.startStation + "," + stationName;
if (!trips.containsKey(tripName)) { // First time someone makes this trip
trips.put(tripName, new Statistic());
}
trips.get(tripName).logTrip(time - checkIn.startTime);
}
public double getAverageTime(String startStation, String endStation) {
String tripName = startStation + "," + endStation;
if (!trips.containsKey(tripName)) return -1; // No such trips
return trips.get(tripName).getAverage();
}
}