🧠
Optimal Approach (Use Custom Linked List for Check-Ins)
💡 This approach uses a linked list to store check-ins to demonstrate linked list based design, useful for interviewers looking for custom data structure usage.
Intuition
Instead of a hash map for check-ins, use a linked list to store ongoing check-ins, and a hash map for route aggregates. This shows mastery of linked list design.
Algorithm
- Maintain a linked list of check-in nodes, each storing id, station, and time.
- On checkIn, append a new node to the linked list.
- On checkOut, traverse the linked list to find the node with the customer's id, remove it, and update route aggregates.
- On getAverageTime, return the average from the route aggregates map.
💡 This algorithm is less efficient for checkOut due to traversal but demonstrates linked list usage and design trade-offs.
class Node:
def __init__(self, id, station, time):
self.id = id
self.station = station
self.time = time
self.next = None
class UndergroundSystem:
def __init__(self):
self.head = None
self.route_data = {}
def checkIn(self, id: int, stationName: str, t: int) -> None:
new_node = Node(id, stationName, t)
new_node.next = self.head
self.head = new_node
def checkOut(self, id: int, stationName: str, t: int) -> None:
prev = None
curr = self.head
while curr:
if curr.id == id:
travel_time = t - curr.time
route = (curr.station, stationName)
if route not in self.route_data:
self.route_data[route] = [0, 0]
self.route_data[route][0] += travel_time
self.route_data[route][1] += 1
if prev:
prev.next = curr.next
else:
self.head = curr.next
return
prev = curr
curr = curr.next
def getAverageTime(self, startStation: str, endStation: str) -> float:
total_time, count = self.route_data.get((startStation, endStation), (0, 0))
return total_time / count if count > 0 else 0.0
# Example usage:
# undergroundSystem = UndergroundSystem()
# undergroundSystem.checkIn(45, "Leyton", 3)
# undergroundSystem.checkOut(45, "Waterloo", 15)
# print(undergroundSystem.getAverageTime("Leyton", "Waterloo")) # Output: 12.0
Line Notes
class Node:Defines a linked list node to store check-in info
self.head = NoneHead pointer for linked list of check-ins
new_node.next = self.headInsert new check-in at head for O(1) insertion
while curr:Traverse linked list to find check-in node on check-out
if curr.id == id:Identify the node to remove
self.route_data[route][0] += travel_timeUpdate total travel time for route
self.route_data[route][1] += 1Update trip count for route
if prev: prev.next = curr.next else: self.head = curr.nextRemove node from linked list
class UndergroundSystem {
private static class Node {
int id, time;
String station;
Node next;
Node(int id, String station, int time) {
this.id = id; this.station = station; this.time = time; this.next = null;
}
}
private Node head;
private Map<String, int[]> routeData;
public UndergroundSystem() {
head = null;
routeData = new HashMap<>();
}
public void checkIn(int id, String stationName, int t) {
Node newNode = new Node(id, stationName, t);
newNode.next = head;
head = newNode;
}
public void checkOut(int id, String stationName, int t) {
Node prev = null, curr = head;
while (curr != null) {
if (curr.id == id) {
int travelTime = t - curr.time;
String route = curr.station + "->" + stationName;
routeData.putIfAbsent(route, new int[2]);
int[] data = routeData.get(route);
data[0] += travelTime;
data[1] += 1;
if (prev != null) {
prev.next = curr.next;
} else {
head = curr.next;
}
return;
}
prev = curr;
curr = curr.next;
}
}
public double getAverageTime(String startStation, String endStation) {
String route = startStation + "->" + endStation;
int[] data = routeData.getOrDefault(route, new int[2]);
return data[1] == 0 ? 0.0 : (double) data[0] / data[1];
}
/* Example usage:
public static void main(String[] args) {
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkOut(45, "Waterloo", 15);
System.out.println(undergroundSystem.getAverageTime("Leyton", "Waterloo")); // 12.0
}
*/
}
Line Notes
private static class NodeDefines linked list node to store check-in info
private Node head;Head pointer for linked list
newNode.next = head; head = newNode;Insert new check-in at head for O(1) insertion
while (curr != null)Traverse linked list to find check-in node on check-out
if (curr.id == id)Identify node to remove
routeData.putIfAbsent(route, new int[2]);Initialize route data if first trip
data[0] += travelTime; data[1] += 1;Update total time and count for route
if (prev != null) { prev.next = curr.next; } else { head = curr.next; }Remove node from linked list
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
class UndergroundSystem {
struct Node {
int id, time;
string station;
Node* next;
Node(int i, string s, int t) : id(i), station(s), time(t), next(nullptr) {}
};
Node* head;
unordered_map<string, pair<long long, int>> routeData;
public:
UndergroundSystem() : head(nullptr) {}
void checkIn(int id, string stationName, int t) {
Node* newNode = new Node(id, stationName, t);
newNode->next = head;
head = newNode;
}
void checkOut(int id, string stationName, int t) {
Node* prev = nullptr;
Node* curr = head;
while (curr) {
if (curr->id == id) {
string route = curr->station + "->" + stationName;
int travelTime = t - curr->time;
routeData[route].first += travelTime;
routeData[route].second += 1;
if (prev) {
prev->next = curr->next;
} else {
head = curr->next;
}
delete curr;
return;
}
prev = curr;
curr = curr->next;
}
}
double getAverageTime(string startStation, string endStation) {
string route = startStation + "->" + endStation;
auto it = routeData.find(route);
if (it == routeData.end() || it->second.second == 0) return 0.0;
return (double)it->second.first / it->second.second;
}
};
/* Example usage:
int main() {
UndergroundSystem undergroundSystem;
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkOut(45, "Waterloo", 15);
cout << undergroundSystem.getAverageTime("Leyton", "Waterloo") << endl; // 12.0
return 0;
}
*/
Line Notes
struct NodeDefines linked list node to store check-in info
Node* head;Head pointer for linked list
newNode->next = head; head = newNode;Insert new check-in at head for O(1) insertion
while (curr)Traverse linked list to find check-in node on check-out
if (curr->id == id)Identify node to remove
routeData[route].first += travelTime;Update total time for route
routeData[route].second += 1;Update trip count for route
if (prev) { prev->next = curr->next; } else { head = curr->next; }Remove node from linked list
delete curr;Free memory of removed node
class Node {
constructor(id, station, time) {
this.id = id;
this.station = station;
this.time = time;
this.next = null;
}
}
class UndergroundSystem {
constructor() {
this.head = null;
this.routeData = new Map();
}
checkIn(id, stationName, t) {
const newNode = new Node(id, stationName, t);
newNode.next = this.head;
this.head = newNode;
}
checkOut(id, stationName, t) {
let prev = null;
let curr = this.head;
while (curr) {
if (curr.id === id) {
const route = curr.station + '->' + stationName;
const travelTime = t - curr.time;
if (!this.routeData.has(route)) {
this.routeData.set(route, [0, 0]);
}
const data = this.routeData.get(route);
data[0] += travelTime;
data[1] += 1;
if (prev) {
prev.next = curr.next;
} else {
this.head = curr.next;
}
return;
}
prev = curr;
curr = curr.next;
}
}
getAverageTime(startStation, endStation) {
const route = startStation + '->' + endStation;
if (!this.routeData.has(route)) return 0.0;
const [totalTime, count] = this.routeData.get(route);
return count === 0 ? 0.0 : totalTime / count;
}
}
// Example usage:
// const undergroundSystem = new UndergroundSystem();
// undergroundSystem.checkIn(45, "Leyton", 3);
// undergroundSystem.checkOut(45, "Waterloo", 15);
// console.log(undergroundSystem.getAverageTime("Leyton", "Waterloo")); // 12.0
Line Notes
class Node {Defines linked list node to store check-in info
this.head = null;Head pointer for linked list
newNode.next = this.head; this.head = newNode;Insert new check-in at head for O(1) insertion
while (curr) {Traverse linked list to find check-in node on check-out
if (curr.id === id) {Identify node to remove
if (!this.routeData.has(route)) { this.routeData.set(route, [0, 0]); }Initialize route data if first trip
data[0] += travelTime; data[1] += 1;Update total time and count for route
if (prev) { prev.next = curr.next; } else { this.head = curr.next; }Remove node from linked list
TimeO(n) for checkOut due to linked list traversal, O(1) for others
SpaceO(n) for linked list and route aggregates
checkOut requires traversing the linked list to find the node, which is linear in number of ongoing check-ins.
💡 For many concurrent check-ins, this approach is slower than hash map but demonstrates linked list design.
Interview Verdict: Accepted but less efficient than hash map approach
This approach is acceptable but not optimal; it shows linked list design skills but is slower for large data.
Recommended