Interview Prepcustom-data-structuresmediumAmazonGoogleFacebook

Design Underground System

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

</>

IDE

def checkIn(self, id: int, stationName: str, t: int) -> None:

class UndergroundSystem:
    def __init__(self):
        pass
    def checkIn(self, id: int, stationName: str, t: int) -> None:
        pass
    def checkOut(self, id: int, stationName: str, t: int) -> None:
        pass
    def getAverageTime(self, startStation: str, endStation: str) -> float:
        pass

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

#include <string>
using namespace std;
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) {
        return 0.0;
    }
};

class UndergroundSystem {
    constructor() {
    }
    checkIn(id, stationName, t) {
    }
    checkOut(id, stationName, t) {
    }
    getAverageTime(startStation, endStation) {
        return 0.0;
    }
}

0/10

Common Bugs to Avoid

Wrong: 0 or error when querying average time with no tripsNot handling empty route data before division✅ Return 0.0 if no trips recorded for the route before dividing

Wrong: Negative or incorrect travel time for same timestamp check-in/outIncorrect time difference calculation or assumptions about time order✅ Compute travel time as checkout time minus checkin time without assumptions

Wrong: Average time incorrect when multiple trips or multiple customersOverwriting check-in data or not accumulating totals correctly✅ Use a map keyed by id for check-ins and accumulate total time and count per route

Wrong: Mixing trips from different routes in average calculationNot separating route keys properly✅ Use (startStation, endStation) as key for totals and counts

Wrong: TLE on large inputsUsing O(n) scan of trips on getAverageTime instead of running totals✅ Maintain running totals and counts per route for O(1) getAverageTime

✓

Test Cases

t1_01basic

Input["checkIn(45, \"Leyton\", 3)","checkOut(45, \"Waterloo\", 15)","getAverageTime(\"Leyton\", \"Waterloo\")"]

Expected"12.0"

Customer 45 checked in at Leyton at time 3 and checked out at Waterloo at time 15, so travel time is 12. Average is 12.0 since only one trip.

t1_02basic

Input

["checkIn(10, \"Leyton\", 5)","checkOut(10, \"Waterloo\", 15)","checkIn(20, \"Leyton\", 10)","checkOut(20, \"Waterloo\", 20)","getAverageTime(\"Leyton\", \"Waterloo\")"]

Expected"10.0"

Two customers traveled from Leyton to Waterloo with times 10 and 10, average is 10.0.

Practice

(1/5)

1. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child lists can themselves have children, and so on. Which approach best guarantees an in-place flattening of this multilevel list into a single-level doubly linked list without using extra space?

easy

A. Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.

B. Use a recursive depth-first traversal that returns the tail of each flattened child list to connect nodes.

C. Apply a greedy approach that always appends child lists at the end of the main list after full traversal.

D. Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.

3. Consider the following buggy implementation of SnapshotArray. Which line contains the subtle bug that can cause incorrect get results when multiple sets occur before a snap on the same index?

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # Bug here
        self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

medium

A. Line in snap(): incrementing snap_id before returning

B. Line in __init__(): initializing with (-1, 0) instead of (0, 0)

C. Line in set(): always appending without checking if last snap_id matches

D. Line in get(): using bisect_right instead of bisect_left

Design Underground System

Start learning this pattern below

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that guarantees in-place flattening without extra space

Step 3: Evaluate other options

Final Answer:

Quick Check:

Solution

Step 1: Identify the costly operation

Step 2: Analyze nested traversal effect

Final Answer:

Quick Check:

Solution

Step 1: Analyze set() method

Step 2: Consequence on get()

Final Answer:

Quick Check:

Solution

Step 1: Understand duplicate handling

Step 2: Evaluate options

Step 3: Reject other options

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem with cycles

Step 2: Identify safe traversal method

Step 3: Evaluate other options

Final Answer:

Quick Check: