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. Consider the following partial Skiplist search method code. After inserting values 1, 3, and 7, what will be the value of curr.val after the outer loop finishes when searching for target = 3?

easy

A. 7

B. 1

C. 3

D. -1

Solution

1. Step 1: Trace outer loop from highest to lowest level

   At each level, move forward while next node's value is less than 3. After finishing, curr points to node with value just less than or equal to 3.

2. Step 2: Move curr to forward[0]

   After the loop, curr moves to forward[0], which should be node with value 3 if it exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Search finds node with value 3 exactly [OK]

Hint: Search stops at node before target, then moves forward once [OK]

Common Mistakes:

• Off-by-one error in loop
• Confusing curr position before and after loop
• Assuming curr stays at head

2. 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

3. What is the average time complexity of the remove operation in the optimized Insert Delete GetRandom O(1) with duplicates data structure that uses a hash map of element to linked list nodes and a list of elements?

medium

A. O(n) because we need to find the element's index in the list before removal.

B. O(log n) due to maintaining the linked list structure during removals.

C. O(1) worst-case because linked list removals and hash map lookups are constant time.

D. O(1) average because the hash map provides direct access to an element's node for removal.

Solution

1. Step 1: Identify data structure operations

   Removal uses hash map to get a node reference in O(1) average time, then removes node from doubly linked list in O(1).

2. Step 2: Clarify average vs worst-case

   Hash map lookups are average O(1), but worst-case can degrade. Linked list removal is always O(1). So overall average is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map + linked list enables average O(1) removals [OK]

Hint: Hash map + linked list enables average O(1) removals [OK]

Common Mistakes:

• Confusing average and worst-case complexities
• Assuming linked list removal is O(log n)
• Thinking index search is needed

4. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)

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