Design Underground System

▶

Steps

setup

Initialize UndergroundSystem

Create an empty UndergroundSystem instance with no check-in nodes and an empty route data map.

💡 Initialization sets the foundation for storing check-ins and route statistics.

Line:

def __init__(self):
    self.head = None
    self.route_data = {}

💡 The system starts with no active check-ins and no recorded routes.

insert

CheckIn: Create new node for customer 45 at Leyton, time 3

A new node is created with id=45, station='Leyton', and time=3 to represent the customer's check-in.

💡 Creating a node encapsulates the check-in data for later retrieval.

Line:

new_node = Node(id, stationName, t)

💡 Each check-in is represented as a node in the linked list.

insert

CheckIn: Link new node to current head

The new node's next pointer is set to the current head (which is null), preparing to insert it at the front.

💡 Linking the new node to the existing list maintains the chain of check-ins.

Line:

new_node.next = self.head

💡 The new node will become the new head, pointing to the previous head.

insert

CheckIn: Update head to new node

The head pointer is updated to point to the new node, making it the first node in the linked list.

💡 Updating head ensures the new check-in is accessible as the start of the list.

Line:

self.head = new_node

💡 The linked list now contains one node representing the active check-in.

traverse

CheckOut: Start traversal from head to find id 45

Begin traversing the linked list from head to find the node with id=45 for check-out.

💡 Traversal is needed to locate the check-in node to remove it and update route data.

Line:

prev = None
curr = self.head

💡 Two pointers, prev and curr, help track the current node and its predecessor during traversal.

compare

CheckOut: Compare curr.id with target id 45

Check if the current node's id matches the id to check out (45). It matches, so proceed to update route data.

💡 This comparison finds the exact node to remove and update travel time.

Line:

if curr.id == id:

💡 Finding the node means we can now calculate travel time and unlink the node.

prune

CheckOut: Calculate travel time and update route_data

Calculate travel time as 15 - 3 = 12 and update route_data for ('Leyton', 'Waterloo') with total time and count.

💡 Updating route_data accumulates total travel time and trip count for average calculation.

Line:

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

💡 Route statistics are updated incrementally with each completed trip.

delete

CheckOut: Remove node from linked list (node is head)

Since prev is None, update head to curr.next (null), effectively removing the node from the list.

💡 Removing the node frees the check-in record as the trip is complete.

Line:

if prev:
    prev.next = curr.next
else:
    self.head = curr.next

💡 Removing the head node updates the list to reflect active check-ins correctly.

compare

GetAverageTime: Retrieve total time and count for route

Look up the route ('Leyton', 'Waterloo') in route_data to get total travel time and trip count.

💡 Accessing stored aggregates allows quick average time calculation.

Line:

total_time, count = self.route_data.get((startStation, endStation), (0, 0))

💡 Route data is stored as total time and count pairs for efficient average computation.

reconstruct

GetAverageTime: Calculate and return average travel time

Calculate average as total_time / count = 12 / 1 = 12.0 and return this value as the answer.

💡 The average travel time is the key output of the system for the queried route.

Line:

return total_time / count if count > 0 else 0.0

💡 The system efficiently computes averages from aggregated data without re-traversing check-ins.

class Node:
    def __init__(self, id, station, time):
        self.id = id  # STEP 2
        self.station = station  # STEP 2
        self.time = time  # STEP 2
        self.next = None

class UndergroundSystem:
    def __init__(self):
        self.head = None  # STEP 1
        self.route_data = {}  # STEP 1

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        new_node = Node(id, stationName, t)  # STEP 2
        new_node.next = self.head  # STEP 3
        self.head = new_node  # STEP 4

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        prev = None  # STEP 5
        curr = self.head  # STEP 5
        while curr:
            if curr.id == id:  # STEP 6
                travel_time = t - curr.time  # STEP 7
                route = (curr.station, stationName)  # STEP 7
                if route not in self.route_data:  # STEP 7
                    self.route_data[route] = [0, 0]  # STEP 7
                self.route_data[route][0] += travel_time  # STEP 7
                self.route_data[route][1] += 1  # STEP 7
                if prev:  # STEP 8
                    prev.next = curr.next  # STEP 8
                else:
                    self.head = curr.next  # STEP 8
                return
            prev = curr  # STEP 5 loop
            curr = curr.next  # STEP 5 loop

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total_time, count = self.route_data.get((startStation, endStation), (0, 0))  # STEP 9
        return total_time / count if count > 0 else 0.0  # STEP 10

# Example usage:
# undergroundSystem = UndergroundSystem()
# undergroundSystem.checkIn(45, "Leyton", 3)
# undergroundSystem.checkOut(45, "Waterloo", 15)
# print(undergroundSystem.getAverageTime("Leyton", "Waterloo"))

📊

Design Underground System - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and node operation reveals how the linked list manages active check-ins efficiently and how route statistics are updated dynamically.

initialize

create_node

Id:45

Station:Leyton

Time:3

connect

Id:45

Station:Leyton

Time:3

advance

Id:45

Station:Leyton

Time:3

traverse

Id:45

Station:Leyton

Time:3

compare

Id:45

Station:Leyton

Time:3

prune

Id:45

Station:Leyton

Time:3

Result:

Route data:

Leyton → Waterloo:[12, 1]

detach

Result:

Route data:

Leyton → Waterloo:[12, 1]

compare

Result:

Route data:

Leyton → Waterloo:[12, 1]

reconstruct

Result: 12

Key Takeaways

✓ Using a linked list to store active check-ins allows efficient insertion and removal without extra hash maps.

This insight is hard to see from code alone because the linked list pointer updates and traversal are subtle and visualizing them clarifies the data structure's dynamic nature.

✓ Traversal with prev and curr pointers is essential to find and remove the correct check-in node during check-out.

Seeing each pointer move and comparison step-by-step helps understand how nodes are unlinked safely without losing list integrity.

✓ Route travel times are aggregated incrementally, enabling constant-time average queries without re-traversing check-ins.

The trace shows how route_data updates after each trip, clarifying the separation of concerns between active check-ins and route statistics.

Practice

1. You need to design a data structure that supports inserting elements (including duplicates), removing one occurrence of an element, and retrieving a random element--all in average O(1) time. Which approach best guarantees these time complexities?

easy

A. Use a simple list and perform linear search for removals.

B. Use a balanced binary search tree to maintain elements and their counts.

C. Use a hash map to store element to indices mapping, combined with a list to store elements, updating indices on insert and remove.

D. Use a queue to track insertion order and a hash set for membership checks.

Solution

1. Step 1: Understand the operations required

   Insert, remove (one occurrence), and getRandom must all be average O(1), even with duplicates.

2. Step 2: Evaluate approaches

   A simple list with linear search (A) leads to O(n) removals. Balanced BST (C) has O(log n) operations. Queue and hash set (D) do not support random access efficiently. Hash map + list with index tracking (B) supports O(1) insert, remove, and getRandom by maintaining indices of duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + list with index tracking enables O(1) average operations [OK]

Hint: Hash map + list with index tracking enables O(1) ops [OK]

Common Mistakes:

• Assuming balanced BST can do O(1) getRandom
• Using linear search for removal
• Ignoring duplicates in data structure

2. Given the following code snippet for SnapshotArray, what is the output of snapshotArr.get(0, 0) after executing all lines shown?

snapshotArr = SnapshotArray(3)
snapshotArr.set(0, 5)
snap_id = snapshotArr.snap()
snapshotArr.set(0, 6)
print(snapshotArr.get(0, 0))

easy

A. 5

B. 6

C. 0

D. Error due to invalid snap_id

Solution

1. Step 1: Trace set and snap operations

   Initially, data[0] = [(-1,0)]. After set(0,5), data[0] = [(-1,0),(0,5)] because snap_id=0. Then snap() increments snap_id to 1 and returns 0. Then set(0,6) appends (1,6) to data[0].

2. Step 2: Trace get(0,0)

   For snap_id=0, bisect_right finds insertion point for (0,inf) in data[0] = [(-1,0),(0,5),(1,6)]. It returns index 2, so i=1. data[0][1] = (0,5), so get returns 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Value at snap 0 is 5, not the later set 6 [OK]

Hint: Get returns value at or before snap_id using binary search [OK]

Common Mistakes:

• Returning latest value ignoring snap_id
• Off-by-one in bisect index

3. What is the space complexity of the optimal approach that copies a linked list with random pointers by interleaving copied nodes within the original list?

medium

A. O(1) because no extra data structures proportional to n are used

B. O(n) due to storing all copied nodes in a hash map

C. O(n) due to recursion stack in the copying process

D. O(n) because of auxiliary arrays used to track random pointers

Solution

1. Step 1: Identify auxiliary data structures

   The optimal approach does not use hash maps or arrays; it weaves copied nodes into the original list.

2. Step 2: Analyze space usage

   Only a few pointers are used; no extra space proportional to n is allocated, so space complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No hash maps or recursion stacks used [OK]

Hint: Interleaving nodes avoids extra space [OK]

Common Mistakes:

• Assuming hash map is always needed, so O(n) space
• Confusing recursion stack space with iterative approach
• Thinking auxiliary arrays are used for random pointers

4. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings? Assume merging two skylines of total length m takes O(m) time.

medium

A. O(n²)

B. O(n)

C. O(n log n)

D. O(n * w) where w is the width of the skyline

Solution

1. Step 1: Identify divide and conquer recurrence

   The algorithm splits buildings into halves recursively, then merges skylines in O(m) time where m is proportional to n.

2. Step 2: Solve recurrence and analyze merge cost

   Recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The width w does not affect complexity here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) [OK]

Hint: Divide and conquer recurrence T(n)=2T(n/2)+O(n) -> O(n log n) [OK]

Common Mistakes:

• Confusing width w with n
• Assuming quadratic due to nested loops

5. Suppose the RangeModule must support intervals with negative coordinates and allow intervals to be added and removed multiple times (reusing intervals). Which modification to the optimal balanced BST approach is necessary to handle this correctly?

hard

A. Replace balanced BST with a segment tree to handle negative and overlapping intervals efficiently.

B. Use a hash map keyed by interval length instead of start points to speed up queries.

C. No modification needed; the existing balanced BST approach handles negative and reused intervals naturally.

D. Store intervals as half-open [start, end) and adjust bisect searches to handle negative values correctly.

Solution

1. Step 1: Consider negative coordinates impact

   Bisect operations and interval storage must correctly handle negative values, which requires no change in data structure but careful handling of interval boundaries.

2. Step 2: Consider interval reuse

   Intervals can be added and removed multiple times, so storing intervals as half-open [start, end) and merging intervals correctly remains essential.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adjust bisect and interval representation for negatives and reuse [OK]

Hint: Half-open intervals and bisect handle negatives and reuse correctly [OK]

Common Mistakes:

• Thinking data structure must change to segment tree unnecessarily