Skip to content

22. Challenge Yourself#

These problems sit at the intersection of multiple DSA patterns. They are the capstone of this guide: you must design a data structure (or combine several) so that every operation meets a strict time bound. Expect hash maps, linked lists, heaps, binary search, and interval logic in the same solution.

Use this section after you have worked through the individual pattern chapters. For each problem, identify which patterns it combines before reading the solution.

Design Data Structure#

Problem Primary patterns combined
LRU Cache (146) Hash Map · Linked List
LFU Cache (460) Hash Map · Linked List · Greedy (min-freq tracking)
Insert Delete GetRandom O(1) (380) Hash Map · Array
Time Based Key-Value Store (981) Hash Map · Binary Search
Snapshot Array (1146) Hash Map · Array (lazy versioning)
Design Twitter (355) Hash Map · Heap · K-way Merge
Design Underground System (1396) Hash Map · Prefix Sum (running aggregates)
Range Module (715) Overlapping Intervals · Binary Search (sorted structure)
Find Median from Data Stream (295) Heaps (two-heap pattern)
Design Browser History (1472) Linked List · Stack-like navigation

Problem 1: LRU Cache (Leetcode:146)#

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 104
  • 0 <= value <= 105
  • At most 2 * 105 calls will be made to get and put.

Patterns: Hash Map · Linked List

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Node:
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev: "Node | None" = None
        self.next: "Node | None" = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, Node] = {}
        self.head = Node()  # dummy head (MRU side)
        self.tail = Node()  # dummy tail (LRU side)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_front(node)
        else:
            if len(self.cache) >= self.cap:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_front(node)
Explanation:

  1. A hash map gives O(1) lookup by key; a doubly linked list orders nodes by recency.
  2. Dummy head/tail nodes avoid null checks. MRU sits near head, LRU near tail.
  3. On get or put hit: remove the node and splice it to the front (mark most recent).
  4. On put miss when full: evict the node before tail (LRU), then insert the new entry at the front.

Time: O(1) per operation · Space: O(capacity)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # mark as most recent
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # evict LRU (oldest)
Explanation:

  1. OrderedDict maintains insertion order and supports move_to_end in O(1).
  2. popitem(last=False) removes the oldest (LRU) entry.
  3. Ideal for interviews in Python; Approach 1 is what you should implement in Java/C++.

Time: O(1) per operation · Space: O(capacity)

Problem 2: LFU Cache (Leetcode:460)#

Problem Statement

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

  • LFUCache(int capacity) Initializes the object with the capacity of the data structure.
  • int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
  • void put(int key, int value) Update the value of the key if present, or insert the key-value pair. When the cache reaches its capacity, it should invalidate and remove the least frequently used key. If there is a tie, remove the least recently used key among them.

The functions get and put must run in O(1) average time complexity.

Example 1:

Input: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Constraints:

  • 1 <= capacity <= 104
  • 0 <= key <= 105
  • 0 <= value <= 109
  • At most 105 calls will be made to get and put.

Patterns: Hash Map · Linked List · Greedy (track global min frequency)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from collections import defaultdict

class Node:
    def __init__(self, key: int = 0, val: int = 0, freq: int = 0):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev: "Node | None" = None
        self.next: "Node | None" = None

class DLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_front(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def remove_back(self) -> Node:
        node = self.tail.prev
        self.remove(node)
        return node

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.min_freq = 0
        self.key_to_node: dict[int, Node] = {}
        self.freq_to_list: dict[int, DLinkedList] = defaultdict(DLinkedList)

    def _update(self, node: Node) -> None:
        freq = node.freq
        self.freq_to_list[freq].remove(node)
        if freq == self.min_freq and self.freq_to_list[freq].size == 0:
            self.min_freq += 1
        node.freq += 1
        self.freq_to_list[node.freq].add_front(node)

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        self._update(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self._update(node)
            return
        if len(self.key_to_node) >= self.cap:
            lfu_list = self.freq_to_list[self.min_freq]
            evicted = lfu_list.remove_back()
            del self.key_to_node[evicted.key]
        node = Node(key, value, 1)
        self.key_to_node[key] = node
        self.freq_to_list[1].add_front(node)
        self.min_freq = 1
Explanation:

  1. Track each key's node in a hash map; group nodes by frequency in doubly linked lists (one list per frequency).
  2. Maintain min_freq — the global minimum frequency currently in the cache.
  3. On access: remove node from its old freq list; if that list empties and it was min_freq, increment min_freq; bump freq and push to front of the new freq list.
  4. On insert when full: evict the back of the min_freq list (least recently used among tied frequencies).

Time: O(1) per operation · Space: O(capacity)

key_to_node: {1 → Node(val=1, freq=2), 2 → Node(val=2, freq=1), ...}

freq=1:  tail ← [2] ← head
freq=2:  tail ← [1] ← head
min_freq = 1
Explanation:

  1. Think of LRU per frequency level: each frequency bucket is a mini-LRU cache.
  2. Eviction always targets freq_to_list[min_freq] — the least frequent, and within that bucket the LRU end.
  3. This is strictly harder than LRU Cache because you juggle two ordering criteria with O(1) updates.

Time: O(1) per operation · Space: O(capacity)

Problem 3: Insert Delete GetRandom O(1) (Leetcode:380)#

Problem Statement

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set. Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, 2, true, false, 2]

Constraints:

  • -231 <= val <= 231 - 1
  • At most 2 * 105 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the structure when getRandom is called.

Patterns: Hash Map · Array

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import random

class RandomizedSet:
    def __init__(self):
        self.nums: list[int] = []
        self.idx: dict[int, int] = {}  # val → index in nums

    def insert(self, val: int) -> bool:
        if val in self.idx:
            return False
        self.idx[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.idx:
            return False
        i = self.idx[val]
        last = self.nums[-1]
        self.nums[i] = last
        self.idx[last] = i
        self.nums.pop()
        del self.idx[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)
Explanation:

  1. Array enables O(1) random index pick; hash map maps value → index for O(1) lookup.
  2. Delete is the trick: swap the target with the last element, update the moved element's index, then pop — O(1) without shifting.
  3. Follow-up 380 + duplicates (381) uses dict[val, set of indices] and the same swap logic per index.

Time: O(1) average per operation · Space: O(n)

Structure insert remove getRandom
set O(1) O(1) O(n) — no random index
list O(1) append O(n) — search + shift O(1)
list + dict O(1) O(1) swap O(1)

Explanation:

  1. Each operation alone is easy; the challenge is satisfying all three in O(1) simultaneously.
  2. The swap-with-last invariant keeps the array dense with no holes.

Time: O(1) average · Space: O(n)

Problem 4: Time Based Key-Value Store (Leetcode:981)#

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

  • TimeMap() Initializes the object.
  • void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
  • String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Example 1:

Input: ["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

Constraints:

  • 1 <= key.length, value.length <= 100
  • key and value consist of lowercase English letters and digits.
  • 1 <= timestamp <= 107
  • All timestamps of set are strictly increasing.
  • At most 2 * 105 calls will be made to set and get.

Patterns: Hash Map · Binary Search

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import bisect
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.store: dict[str, list[tuple[int, str]]] = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        entries = self.store.get(key, [])
        i = bisect.bisect_right(entries, (timestamp, chr(127)))
        if i == 0:
            return ""
        return entries[i - 1][1]
Explanation:

  1. Hash map maps each key to a list of (timestamp, value) pairs sorted by timestamp (guaranteed by strictly increasing set calls).
  2. Binary search (bisect_right) finds the rightmost timestamp ≤ query — classic "floor" search on a sorted array.
  3. The sentinel chr(127) in the tuple ensures we compare timestamps first, then break ties by value (irrelevant when timestamps are unique).

Time: O(1) set · O(log n) get per key · Space: O(total entries)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.store: dict[str, list[tuple[int, str]]] = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        entries = self.store.get(key, [])
        lo, hi = 0, len(entries) - 1
        ans = ""
        while lo <= hi:
            mid = (lo + hi) // 2
            if entries[mid][0] <= timestamp:
                ans = entries[mid][1]
                lo = mid + 1
            else:
                hi = mid - 1
        return ans
Explanation:

  1. Standard lower-bound / floor binary search: shrink the right side when entries[mid].timestamp > query.
  2. Keep the best candidate in ans whenever entries[mid].timestamp <= timestamp.
  3. Equivalent to bisect; use this form when bisect is unavailable.

Time: O(1) set · O(log n) get · Space: O(total entries)

Problem 5: Snapshot Array (Leetcode:1146)#

Problem Statement

Implement a SnapshotArray that supports the following interface:

  • SnapshotArray(int length) Initializes an array-like data structure with the given length. Initially, each element equals 0.
  • void set(index, val) Sets the element at the given index to be equal to val.
  • int snap() Takes a snapshot of the array and returns the snap_id (incremental ID assigned to the snapshot starting from 0).
  • int get(index, snap_id) Returns the value at index at the time the snapshot with snap_id was taken.

Example 1:

Input: ["SnapshotArray", "set", "snap", "get", "set", "snap", "get"]
[[3], [0, 5], [], [0, 0], [0, 6], [], [0, 1]]
Output: [null, null, 0, 5, null, 0, 6]

Constraints:

  • 1 <= length <= 5 * 104
  • 0 <= index < length
  • 0 <= val <= 109
  • 0 <= snap_id < snap() calls
  • At most 5 * 104 calls will be made to set, snap, and get.

Patterns: Hash Map · Array (lazy versioning) · Binary Search

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.history: list[list[tuple[int, int]]] = [[(0, 0)] for _ in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        self.history[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:
        entries = self.history[index]
        i = bisect.bisect_right(entries, (snap_id, float("inf"))) - 1
        return entries[i][1]
Explanation:

  1. Never copy the full array on snap — only increment a counter. Each index stores a sorted list of (snap_id, value) changes.
  2. (0, 0) seeds every index with the initial zero at snapshot 0.
  3. get(index, snap_id) uses binary search to find the latest change with change_snap ≤ snap_id.

Time: O(1) set · O(1) snap · O(log k) get (k = changes per index) · Space: O(length + total sets)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class SnapshotArray:
    def __init__(self, length: int):
        self.arr = [0] * length
        self.snaps: list[list[int]] = []

    def set(self, index: int, val: int) -> None:
        self.arr[index] = val

    def snap(self) -> int:
        self.snaps.append(self.arr[:])
        return len(self.snaps) - 1

    def get(self, index: int, snap_id: int) -> int:
        return self.snaps[snap_id][index]
Explanation:

  1. Deep-copy the array on every snap — O(n) per snapshot.
  2. Correct and easy to explain, but fails when snap() is called frequently on large arrays.
  3. Approach 1 is the intended design: lazy versioning with per-cell history.

Time: O(n) snap · O(1) get · Space: O(n × num_snaps)

Problem 6: Design Twitter (Leetcode:355)#

Problem Statement

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweet ids in the user's news feed.

Implement the Twitter class:

  • Twitter() Initializes your twitter object.
  • void postTweet(int userId, int tweetId) Creates a new tweet with ID tweetId by the user userId. Each call will be made with a unique tweetId.
  • List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's feed. Each item must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
  • void follow(int followerId, int followeeId) The user with ID followerId follows the user with ID followeeId.
  • void unfollow(int followerId, int followeeId) The user with ID followerId unfollowed the user with ID followeeId.

Example 1:

Input: ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
Output: [null, null, [5], null, null, [6, 5], null, [5]]

Constraints:

  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 104
  • All tweets have unique IDs.
  • At most 3 * 104 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

Patterns: Hash Map · Heap · K-way Merge

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets: dict[int, list[tuple[int, int]]] = defaultdict(list)
        self.following: dict[int, set[int]] = defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1

    def getNewsFeed(self, userId: int) -> list[int]:
        users = self.following[userId] | {userId}
        heap = []
        for uid in users:
            if self.tweets[uid]:
                t, tid = self.tweets[uid][-1]
                heapq.heappush(heap, (-t, tid, uid, len(self.tweets[uid]) - 1))
        feed = []
        while heap and len(feed) < 10:
            _, tid, uid, idx = heapq.heappop(heap)
            feed.append(tid)
            if idx > 0:
                t, prev_tid = self.tweets[uid][idx - 1]
                heapq.heappush(heap, (-t, prev_tid, uid, idx - 1))
        return feed

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)
Explanation:

  1. Store each user's tweets as a chronologically sorted list with a global timestamp counter.
  2. getNewsFeed is a k-way merge: seed a min-heap (negate time for max-heap) with each followed user's latest tweet.
  3. Pop the most recent, push that user's next-older tweet — same pattern as K-way Merge / merge k sorted lists. Stop after 10.

Time: O(1) post/follow/unfollow · O(F log F) feed (F ≤ 11 users, capped at 10 pops) · Space: O(total tweets + follows)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets: dict[int, list[tuple[int, int]]] = defaultdict(list)
        self.following: dict[int, set[int]] = defaultdict(set)
        self.feeds: dict[int, list[int]] = defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1
        for follower in self.following:
            if userId in self.following[follower] or follower == userId:
                f = self.feeds[follower]
                f.insert(0, tweetId)
                del f[10:]

    def getNewsFeed(self, userId: int) -> list[int]:
        return self.feeds[userId][:10]

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)
Explanation:

  1. Push each new tweet into every follower's precomputed feed on postTweet.
  2. getNewsFeed becomes O(1), but postTweet can be O(users × followers) — bad at scale.
  3. Approach 1 (heap merge on read) is the standard interview answer.

Time: O(1) getNewsFeed · O(U) postTweet · Space: O(total stored feed entries)

Problem 7: Design Underground System (Leetcode:1396)#

Problem Statement

An underground railway system tracks customer travel times between different stations. Implement the UndergroundSystem class:

  • void checkIn(int id, string stationName, int t) A customer with id id checks in at station stationName at time t.
  • void checkOut(int id, string stationName, int t) A customer with id id checks out from station stationName at time t.
  • double getAverageTime(string startStation, string endStation) Returns the average time taken to travel from startStation to endStation across all previous trips.

Example 1:

Input: ["UndergroundSystem", "checkIn", "checkIn", "checkIn", "checkOut", "checkOut", "checkOut", "getAverageTime", "getAverageTime", "checkIn", "getAverageTime", "checkOut", "getAverageTime"]
[[], [45, "Leyton", 3], [32, "Paradise", 8], [27, "Leyton", 10], [45, "Waterloo", 15], [27, "Waterloo", 20], [32, "Cambridge", 22], ["Paradise", "Cambridge"], ["Leyton", "Waterloo"], [10, "Leyton", 24], ["Leyton", "Waterloo"], [10, "Waterloo", 38], ["Leyton", "Waterloo"]]
Output: [null, null, null, null, null, null, null, 14.0, 11.0, null, 11.0, null, 12.0]

Constraints:

  • 1 <= id, t <= 106
  • All strings consist of uppercase and lowercase English letters and digits.
  • 1 <= stationName.length <= 10
  • At most 2 * 104 calls will be made to checkIn, checkOut, and getAverageTime.
  • Answers within 10-5 of the actual value will be accepted.

Patterns: Hash Map · Prefix Sum (running total / count aggregates)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from collections import defaultdict

class UndergroundSystem:
    def __init__(self):
        self.check_ins: dict[int, tuple[str, int]] = {}
        self.routes: dict[tuple[str, str], list[int]] = defaultdict(lambda: [0, 0])

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_ins[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start, start_time = self.check_ins.pop(id)
        route = (start, stationName)
        self.routes[route][0] += t - start_time
        self.routes[route][1] += 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total, count = self.routes[(startStation, endStation)]
        return total / count
Explanation:

  1. Hash map 1 tracks in-progress trips: id → (start_station, start_time).
  2. Hash map 2 aggregates each directed route (start, end) → [total_time, trip_count] — a running prefix sum style aggregate.
  3. No need to store individual trip durations; update totals on checkout and divide on query.

Time: O(1) per operation · Space: O(active users + distinct routes)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from collections import defaultdict

class UndergroundSystem:
    def __init__(self):
        self.check_ins: dict[int, tuple[str, int]] = {}
        self.trips: dict[tuple[str, str], list[int]] = defaultdict(list)

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_ins[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start, start_time = self.check_ins.pop(id)
        self.trips[(start, stationName)].append(t - start_time)

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        durations = self.trips[(startStation, endStation)]
        return sum(durations) / len(durations)
Explanation:

  1. Append each trip duration to a list per route; average = sum / len on query.
  2. getAverageTime becomes O(k) in the number of trips for that route.
  3. Approach 1 is preferred — O(1) query with incremental aggregation.

Time: O(1) checkIn/Out · O(k) getAverageTime · Space: O(total trips)

Problem 8: Range Module (Leetcode:715)#

Problem Statement

A range module tracks half-open intervals [left, right). Implement the RangeModule class:

  • void addRange(int left, int right) Adds [left, right) to the module.
  • boolean queryRange(int left, int right) Returns true if [left, right) is fully covered.
  • void removeRange(int left, int right) Removes [left, right) from the module.

Example 1:

Input: ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "addRange", "queryRange", "queryRange", "removeRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 22], [21, 22], [15, 17], [16, 17], [16, 17]]
Output: [null, null, null, true, false, null, true, false, null, true]

Constraints:

  • 1 <= left < right <= 109
  • At most 104 calls will be made to addRange, queryRange, and removeRange.

Patterns: Overlapping Intervals · Binary Search (sorted interval list)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import bisect

class RangeModule:
    def __init__(self):
        self.intervals: list[list[int]] = []

    def addRange(self, left: int, right: int) -> None:
        i = 0
        merged: list[list[int]] = []
        while i < len(self.intervals) and self.intervals[i][1] < left:
            merged.append(self.intervals[i])
            i += 1
        while i < len(self.intervals) and self.intervals[i][0] <= right:
            left = min(left, self.intervals[i][0])
            right = max(right, self.intervals[i][1])
            i += 1
        merged.append([left, right])
        merged.extend(self.intervals[i:])
        self.intervals = merged

    def queryRange(self, left: int, right: int) -> bool:
        i = bisect.bisect_left(self.intervals, [left, left])
        if i < len(self.intervals) and self.intervals[i][0] <= left:
            return self.intervals[i][1] >= right
        if i > 0 and self.intervals[i - 1][1] >= right:
            return True
        return False

    def removeRange(self, left: int, right: int) -> None:
        result: list[list[int]] = []
        for lo, hi in self.intervals:
            if hi <= left or lo >= right:
                result.append([lo, hi])
            else:
                if lo < left:
                    result.append([lo, left])
                if hi > right:
                    result.append([right, hi])
        self.intervals = result
Explanation:

  1. Maintain a sorted, non-overlapping list of half-open intervals — classic Overlapping Intervals merge logic.
  2. addRange: skip intervals entirely left of the new range, merge overlapping/touching ones, append the expanded range, then copy the rest.
  3. queryRange: binary search for the interval containing left; check if it (or the previous interval) covers through right.
  4. removeRange: split any interval that partially overlaps the removal window.

Time: O(n) add/remove · O(log n) query · Space: O(n)

Explanation:

  1. In Java, TreeMap<Integer, Integer> mapping start → end gives O(log n) add/remove/query via ceiling/floor keys.
  2. In Python, sortedcontainers.SortedList achieves the same; the manual list above is interview-portable without extra libraries.
  3. Segment trees also work but are overkill for ≤ 10⁴ operations — interval merging is the intended pattern.

Time: O(log n) per operation with balanced tree · Space: O(n)

Problem 9: Find Median from Data Stream (Leetcode:295)#

Problem Statement

The median is the middle value in an ordered list. For a stream of integers, implement a data structure that supports:

  • MedianFinder() Initializes the object.
  • void addNum(int num) Adds the integer num from the data stream to the data structure.
  • double findMedian() Returns the median of all elements so far.

Example 1:

Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output: [null, null, null, 1.5, null, 2.0]

Constraints:

  • -105 <= num <= 105
  • At most 5 * 104 calls will be made to addNum and findMedian.
  • It is guaranteed that there will be at least one element before calling findMedian.

Patterns: Heaps (two-heap / running median)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import heapq

class MedianFinder:
    def __init__(self):
        self.lo: list[int] = []  # max-heap (negate values)
        self.hi: list[int] = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0
Explanation:

  1. Split numbers into two halves: lo (max-heap, lower half) and hi (min-heap, upper half).
  2. Invariant: every value in lo ≤ every value in hi, and |len(lo) - len(hi)| ≤ 1.
  3. Push to lo, balance by moving the max of lo to hi, then rebalance sizes if needed.
  4. Median is the top of the larger heap (odd count) or the average of both tops (even count). See Heaps — Two Heaps.

Time: O(log n) addNum · O(1) findMedian · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import bisect

class MedianFinder:
    def __init__(self):
        self.nums: list[int] = []

    def addNum(self, num: int) -> None:
        bisect.insort(self.nums, num)

    def findMedian(self) -> float:
        n = len(self.nums)
        if n % 2:
            return float(self.nums[n // 2])
        return (self.nums[n // 2 - 1] + self.nums[n // 2]) / 2.0
Explanation:

  1. Keep a sorted list; insert with bisect.insort — O(n) per add due to shifting.
  2. Correct and easy to code under time pressure for small inputs.
  3. Two-heap approach is the intended O(log n) design.

Time: O(n) addNum · O(1) findMedian · Space: O(n)

Problem 10: Design Browser History (Leetcode:1472)#

Problem Statement

You have a browser of one tab where you start on the homepage and can visit another URL, go back steps times, or go forward steps times.

Implement the BrowserHistory class:

  • BrowserHistory(string homepage) Initializes with the homepage.
  • void visit(string url) Visits url from the current page. All forward history is cleared.
  • string back(int steps) Move steps back in history. If you can only back x steps, return the page after x back.
  • string forward(int steps) Move steps forward. Same rule if fewer pages exist ahead.

Example 1:

Input: ["BrowserHistory", "visit", "visit", "visit", "back", "back", "forward", "visit", "forward", "back", "back"]
[["leetcode.com"], ["google.com"], ["facebook.com"], ["youtube.com"], [1], [1], [1], ["linkedin.com"], [2], [2], [7]]
Output: [null, null, null, null, "facebook.com", "google.com", "facebook.com", null, "linkedin.com", "google.com", "leetcode.com"]

Constraints:

  • 1 <= homepage.length <= 20
  • 1 <= url.length <= 20
  • 1 <= steps <= 100
  • At most 5000 calls.

Patterns: Linked List · Stack-like navigation (array + pointer)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.cur = 0

    def visit(self, url: str) -> None:
        self.history = self.history[: self.cur + 1]
        self.history.append(url)
        self.cur += 1

    def back(self, steps: int) -> str:
        self.cur = max(0, self.cur - steps)
        return self.history[self.cur]

    def forward(self, steps: int) -> str:
        self.cur = min(len(self.history) - 1, self.cur + steps)
        return self.history[self.cur]
Explanation:

  1. Model history as an array with a pointer cur — same mental model as a linked list with forward/back links, but simpler in Python.
  2. visit truncates forward history (history[:cur+1]) then appends — like clearing the forward stack in a browser.
  3. back / forward clamp the pointer to valid bounds and return the page at cur.

Time: O(1) back/forward · O(n) visit (truncate copy) · Space: O(total visits)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Node:
    def __init__(self, url: str):
        self.url = url
        self.prev: "Node | None" = None
        self.next: "Node | None" = None

class BrowserHistory:
    def __init__(self, homepage: str):
        self.cur = Node(homepage)

    def visit(self, url: str) -> None:
        node = Node(url)
        node.prev = self.cur
        self.cur.next = node
        self.cur = node

    def back(self, steps: int) -> str:
        while steps and self.cur.prev:
            self.cur = self.cur.prev
            steps -= 1
        return self.cur.url

    def forward(self, steps: int) -> str:
        while steps and self.cur.next:
            self.cur = self.cur.next
            steps -= 1
        return self.cur.url
Explanation:

  1. True doubly linked list: each visit creates a new node and severs the old forward chain automatically (orphaned nodes are GC'd).
  2. Walk prev / next pointers for back and forward — O(steps) per call.
  3. Array + pointer (Approach 1) is usually faster in practice; linked list matches the problem's mental model.

Time: O(steps) back/forward · O(1) visit · Space: O(total visits)