Design Underground System

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Design Underground System

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Requirement

checkIn(id, stationName, t)
checkOut(id, stationName, t)
getAverageTime(startStation, endStation)

Medium

Examples

Input: ["UndergroundSystem","checkIn","checkOut","getAverageTime"]
[[],[45,"a",3],[45,"b",10],["a","b"]]
Output: [null,null,null,7.0]

Approach 1

Level I: Single HashMap with List (Brute Force)

Intuition

Store every check-in and check-out event in a single list or map. When asked for the average, iterate through ALL logged events to find matches. This is slow but memory-efficient for simple logs.

⏱ O(1) write, O(E) read where E is events.💾 O(E).

Detailed Dry Run

Logs: [(id:45, in:'a', out:'b', time:7), (id:46, in:'c', out:'b', time:10)]. Average('a','b') -> find first entry -> 7.

java

class UndergroundSystem {
    class Event { String start, end; int duration; Event(String s, String e, int d) { start = s; end = e; duration = d; } }
    Map<Integer, String[]> active = new HashMap<>();
    List<Event> history = new ArrayList<>();
    public void checkIn(int id, String s, int t) { active.put(id, new String[]{s, String.valueOf(t)}); }
    public void checkOut(int id, String s, int t) {
        String[] in = active.remove(id);
        history.add(new Event(in[0], s, t - Integer.parseInt(in[1])));
    }
    public double getAverageTime(String s, String e) {
        double sum = 0; int count = 0;
        for(Event ev : history) if(ev.start.equals(s) && ev.end.equals(e)) { sum += ev.duration; count++; }
        return sum / count;
    }
}

Approach 2

Level II: String Concatenation Keys

Intuition

Use simple string concatenation start+"->"+end as keys in a single HashMap. Store lists of travel durations and compute averages on the fly.

⏱ O(1) all ops, search is O(K) where K is number of trips.💾 O(N).

java

class UndergroundSystem {
    Map<Integer, Object[]> checkIn = new HashMap<>();
    Map<String, List<Integer>> trips = new HashMap<>();
    public void checkIn(int id, String s, int t) { checkIn.put(id, new Object[]{s, t}); }
    public void checkOut(int id, String s, int t) {
        Object[] cin = checkIn.get(id);
        String key = cin[0] + "->" + s;
        trips.putIfAbsent(key, new ArrayList<>());
        trips.get(key).add(t - (int)cin[1]);
    }
    public double getAverageTime(String start, String end) {
        List<Integer> list = trips.get(start + "->" + end);
        return list.stream().mapToInt(i->i).average().orElse(0.0);
    }
}

Approach 3

Level III: Two HashMaps

Intuition

Use checkInMap to store id -> (station, time). Use routeMap to store (start, end) -> (totalTime, count). Checkout triggers a look-up in checkInMap, calculates the duration, and updates routeMap.

⏱ O(1) for all operations.💾 O(P + S^2) where P is max active passengers, S is stations.

java

class UndergroundSystem {
    class CheckIn { String station; int time; CheckIn(String s, int t) { station = s; time = t; } }
    class Route { double total; int count; }
    Map<Integer, CheckIn> in = new HashMap<>();
    Map<String, Route> rMap = new HashMap<>();
    public void checkIn(int id, String s, int t) { in.put(id, new CheckIn(s, t)); }
    public void checkOut(int id, String s, int t) {
        CheckIn ci = in.remove(id);
        String key = ci.station + "," + s;
        Route rt = rMap.getOrDefault(key, new Route());
        rt.total += (t - ci.time); rt.count++;
        rMap.put(key, rt);
    }
    public double getAverageTime(String start, String end) {
        Route rt = rMap.get(start + "," + end);
        return rt.total / rt.count;
    }
}

← Previous QuestionDesign Add and Search Words

Next Question →Design Snake Game

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.