Interview Prepcustom-data-structuresmediumAmazonGoogleFacebook

Design Underground System

Choose your preparation mode4 modes available

Try It Solution Trace

</>

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 singly linked list where each node contains an additional random pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both next and random pointers. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Sort nodes by their values and then copy them sequentially, assigning random pointers based on sorted order.

B. Use a brute force approach with nested loops to assign random pointers after copying nodes.

C. Use dynamic programming to store intermediate results of copied nodes and their random pointers.

D. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

2. Identify the bug in the following LRU Cache implementation snippet that causes incorrect eviction behavior when capacity is exceeded:

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self._remove(self.cache[key])
    node = Node(key, value)
    self._add(node)
    self.cache[key] = node
    if len(self.cache) > self.capacity:
        lru = self.head.next  # Bug here
        self._remove(lru)
        del self.cache[lru.key]

medium

A. Evicting the node at head.next instead of tail.prev

B. Removing node from cache before adding new node

C. Not updating the cache dictionary after eviction

D. Not checking if capacity is zero before eviction

5. Suppose the data structure must now support a new operation: getRandomWeighted(), which returns a random element with probability proportional to the number of times it appears (its frequency). Which modification to the optimized Insert Delete GetRandom O(1) with duplicates data structure is correct to support this efficiently?

hard

A. Maintain a list with each element repeated as many times as its frequency; getRandomWeighted() picks uniformly from this list.

B. Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove.

C. Use the existing list and hash map without changes; getRandomWeighted() is same as getRandom().

D. Store frequencies in a balanced BST and perform weighted random selection by traversing the tree.

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Design Underground System

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Understand eviction logic

Step 2: Identify bug

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 tweet reuse impact

Step 2: Adjust data structures

Final Answer:

Quick Check:

Solution

Step 1: Understand weighted random requirements

Step 2: Evaluate options

Step 3: Choose best tradeoff

Final Answer:

Quick Check:

Ready to prove it?